{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Arrive at Destination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #dynamic-programming #shortest-path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #动态规划 #最短路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #到达目的地的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你在一个城市里，城市由 <code>n</code>&nbsp;个路口组成，路口编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;，某些路口之间有 <strong>双向</strong>&nbsp;道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;和二维整数数组&nbsp;<code>roads</code>&nbsp;，其中&nbsp;<code>roads[i] = [u<sub>i</sub>, v<sub>i</sub>, time<sub>i</sub>]</code>&nbsp;表示在路口&nbsp;<code>u<sub>i</sub></code>&nbsp;和&nbsp;<code>v<sub>i</sub></code>&nbsp;之间有一条需要花费&nbsp;<code>time<sub>i</sub></code>&nbsp;时间才能通过的道路。你想知道花费 <strong>最少时间</strong>&nbsp;从路口&nbsp;<code>0</code>&nbsp;出发到达路口&nbsp;<code>n - 1</code>&nbsp;的方案数。</p>\n",
    "\n",
    "<p>请返回花费 <strong>最少时间</strong>&nbsp;到达目的地的 <strong>路径数目</strong>&nbsp;。由于答案可能很大，将结果对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/17/graph2.png\" style=\"width: 235px; height: 381px;\">\n",
    "<pre><b>输入：</b>n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>从路口 0 出发到路口 6 花费的最少时间是 7 分钟。\n",
    "四条花费 7 分钟的路径分别为：\n",
    "- 0 ➝ 6\n",
    "- 0 ➝ 4 ➝ 6\n",
    "- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6\n",
    "- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 2, roads = [[1,0,10]]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>只有一条从路口 0 到路口 1 的路，花费 10 分钟。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 200</code></li>\n",
    "\t<li><code>n - 1 &lt;= roads.length &lt;= n * (n - 1) / 2</code></li>\n",
    "\t<li><code>roads[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>1 &lt;= time<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>u<sub>i </sub>!= v<sub>i</sub></code></li>\n",
    "\t<li>任意两个路口之间至多有一条路。</li>\n",
    "\t<li>从任意路口出发，你能够到达其他任意路口。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-arrive-at-destination](https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-arrive-at-destination](https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]', '2\\n[[1,0,10]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        INF = 10 ** 16\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a = [[INF] * n for _ in range(n)]\n",
    "        for road in roads:\n",
    "            a[road[0]][road[1]] = road[2]\n",
    "            a[road[1]][road[0]] = road[2]\n",
    "        c = [_ for _ in a[0]]\n",
    "        count = [1 if _ != INF else 0 for _ in c]\n",
    "        visited = [False] * n\n",
    "        visited[0] = True\n",
    "        for i in range(n - 1):\n",
    "            index = -1\n",
    "            for j in range(1, n):\n",
    "                if not visited[j] and c[j] != INF:\n",
    "                    if index == -1:\n",
    "                        index = j\n",
    "                    elif c[j] < c[index]:\n",
    "                        index = j\n",
    "            if index == n - 1:\n",
    "                return count[n - 1]\n",
    "            visited[index] = True\n",
    "            for j in range(n):\n",
    "                if visited[j] or a[index][j] == INF:\n",
    "                    continue\n",
    "                if c[index] + a[index][j] == c[j]:\n",
    "                    count[j] = (count[j] + count[index]) % MOD\n",
    "                elif c[index] + a[index][j] < c[j]:\n",
    "                    count[j] = count[index]\n",
    "                    c[j] = c[index] + a[index][j]\n",
    "        return count[n - 1]\n",
    "                \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        INF = 10 ** 16\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a = [[INF] * n for _ in range(n)]\n",
    "        for road in roads:\n",
    "            a[road[0]][road[1]] = road[2]\n",
    "            a[road[1]][road[0]] = road[2]\n",
    "        c = [_ for _ in a[0]]\n",
    "        count = [1 if _ != INF else 0 for _ in c]\n",
    "        visited = [False] * n\n",
    "        visited[0] = True\n",
    "        for i in range(n - 1):\n",
    "            index = -1\n",
    "            for j in range(1, n):\n",
    "                if not visited[j] and c[j] != INF:\n",
    "                    if index == -1:\n",
    "                        index = j\n",
    "                    elif c[j] < c[index]:\n",
    "                        index = j\n",
    "            if index == n - 1:\n",
    "                return count[n - 1]\n",
    "            visited[index] = True\n",
    "            for j in range(n):\n",
    "                if visited[j] or a[index][j] == INF:\n",
    "                    continue\n",
    "                if c[index] + a[index][j] == c[j]:\n",
    "                    count[j] = (count[j] + count[index]) % MOD\n",
    "                elif c[index] + a[index][j] < c[j]:\n",
    "                    count[j] = count[index]\n",
    "                    c[j] = c[index] + a[index][j]\n",
    "        return count[n - 1]\n",
    "                \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod=10**9+7\n",
    "        \"\"\"\n",
    "        考虑先求出最短路再统计数目\n",
    "        \"\"\"\n",
    "        g=[[inf]*n for _ in range(n)]\n",
    "        for u,v,w in roads:\n",
    "            g[u][v]=w\n",
    "            g[v][u]=w\n",
    "        vis=[False]*n\n",
    "        dis=[inf]*n\n",
    "        dis[0]=0\n",
    "        while True:\n",
    "            x=-1\n",
    "            for i in range(n):\n",
    "                if not vis[i] and (x<0 or dis[i]<dis[x]):\n",
    "                    x=i\n",
    "            # if x<0 or dis[x]==inf:\n",
    "            #     break\n",
    "            if x==n-1:\n",
    "                break\n",
    "            vis[x]=True\n",
    "            for y,w in enumerate(g[x]):\n",
    "                if dis[x]+w<dis[y]:\n",
    "                    dis[y]=dis[x]+w\n",
    "        deg=[0]*n\n",
    "        for v in range(n):\n",
    "            for u,w in enumerate(g[v]):\n",
    "                if dis[u]==dis[v]+w:\n",
    "                    deg[u]+=1\n",
    "        q=[0]\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        while q:\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for v in tmp:\n",
    "                for u,w in enumerate(g[v]):\n",
    "                    if dis[u]==dis[v]+w:\n",
    "                        dp[u]+=dp[v]%mod\n",
    "                        deg[u]-=1\n",
    "                        if deg[u]==0:\n",
    "                            q.append(u)\n",
    "        return dp[n-1]%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "        dist = [float('inf')] * n\n",
    "        vis = [False] * n\n",
    "        indegs = [0] * n\n",
    "        mod = 10**9 + 7\n",
    "    \n",
    "        def dijkstra():\n",
    "            dist[0] = 0\n",
    "            for _ in range(n):\n",
    "                t = -1\n",
    "                for j in range(n):\n",
    "                    if not vis[j] and (t == -1 or dist[j] < dist[t]):\n",
    "                        t = j\n",
    "                vis[t] = True\n",
    "                for j in range(n):\n",
    "                    if g[t][j] == 0:\n",
    "                        continue\n",
    "                    dist[j] = min(dist[j], dist[t] + g[t][j])\n",
    "        \n",
    "        for info in roads:\n",
    "            i, j, d = info\n",
    "            g[i][j] = g[j][i] = d\n",
    "        dijkstra()\n",
    "\n",
    "        for info in roads:\n",
    "            i, j, d = info\n",
    "            g[i][j] = g[j][i] = 0\n",
    "            if dist[i] + d == dist[j]:\n",
    "                g[i][j] = d\n",
    "                indegs[j] += 1\n",
    "            elif dist[j] + d == dist[i]:\n",
    "                g[j][i] = d\n",
    "                indegs[i] += 1\n",
    "        \n",
    "        q = collections.deque()\n",
    "        for i in range(n):\n",
    "            if indegs[i] == 0:\n",
    "                q.append(i)\n",
    "        \n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for i in range(n):\n",
    "                if g[x][i] == 0:\n",
    "                    continue\n",
    "                dp[i] += dp[x]\n",
    "                indegs[i] -= 1\n",
    "                if indegs[i] == 0:\n",
    "                    q.append(i)\n",
    "        return dp[-1]%mod\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[inf] * n for _ in range(n)]\n",
    "        for a, b, w in roads:\n",
    "            g[a][b] = g[b][a] = w\n",
    "        \n",
    "        # Dijkstra\n",
    "        dis = [inf] * n\n",
    "        dis[0] = 0\n",
    "        vis = [False] * n\n",
    "        for _ in range(n):\n",
    "            x = -1\n",
    "            for i in range(n):\n",
    "                if not vis[i] and (x < 0 or dis[i] < dis[x]):\n",
    "                    x = i\n",
    "            if x < 0: break\n",
    "            vis[x] = True\n",
    "            for y, w in enumerate(g[x]):\n",
    "                d = dis[x] + w\n",
    "                if not vis[y] and d < dis[y]:\n",
    "                    dis[y] = d \n",
    "        # print(dis)\n",
    "\n",
    "        # 拓扑排序\n",
    "        m = [[] for _ in range(n)]\n",
    "        for a, b, w in roads:\n",
    "            if dis[b] - dis[a] == w:\n",
    "                m[a].append(b)\n",
    "            if dis[a] - dis[b] == w:\n",
    "                m[b].append(a)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x == n - 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y in m[x]:\n",
    "                res += dfs(y)\n",
    "            return res\n",
    "        \n",
    "        MOD = 10 ** 9 + 7\n",
    "        return dfs(0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        dist = [[float(\"inf\")] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dist[i][i] = 0\n",
    "        \n",
    "        for x, y, z in roads:\n",
    "            dist[x][y] = dist[y][x] = z\n",
    "        \n",
    "        # Floyd 算法求解最短路\n",
    "        # 完成后，dist[0][i] 即为正文部分的 dist[i]\n",
    "        # for k in range(n):\n",
    "        #     for i in range(n):\n",
    "        #         for j in range(n):\n",
    "        #             dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n",
    "\n",
    "        # Dijkstra 算法求解最短路\n",
    "        # 完成后，dist[0][i] 即为正文部分的 dist[i]\n",
    "        seen = set()\n",
    "        for _ in range(n - 1):\n",
    "            u = None\n",
    "            for i in range(n):\n",
    "                if i not in seen and (not u or dist[0][i] < dist[0][u]):\n",
    "                    u = i\n",
    "            seen.add(u)\n",
    "            for i in range(n):\n",
    "                dist[0][i] = min(dist[0][i], dist[0][u] + dist[u][i])\n",
    "\n",
    "        # 构造图 G\n",
    "        g = defaultdict(list)\n",
    "        for x, y, z in roads:\n",
    "            if dist[0][y] - dist[0][x] == z:\n",
    "                g[x].append(y)\n",
    "            elif dist[0][x] - dist[0][y] == z:\n",
    "                g[y].append(x)\n",
    "\n",
    "        @cache\n",
    "        def dfs(u: int) -> int:\n",
    "            if u == n - 1:\n",
    "                return 1\n",
    "\n",
    "            ret = 0\n",
    "            for v in g[u]:\n",
    "                ret += dfs(v)\n",
    "            return ret % mod\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[inf] * n for _ in range(n)]\n",
    "        for x, y, w in roads:\n",
    "            g[x][y] = g[y][x] = w\n",
    "        \n",
    "        #Dijkstra\n",
    "        dis = [0] + [inf] * (n - 1)\n",
    "        vis = [False] * n\n",
    "        while True:\n",
    "            x = -1\n",
    "            for i in range(n):\n",
    "                if not vis[i] and (x < 0 or dis[i] < dis[x]):\n",
    "                    x = i \n",
    "            if x == -1 : break\n",
    "            vis[x] = True\n",
    "            for y, w in enumerate(g[x]):\n",
    "                if dis[x] + w < dis[y]:\n",
    "                    dis[y] = dis[x] + w \n",
    "                    \n",
    "\n",
    "        print(dis)\n",
    "\n",
    "        # 拓扑排序\n",
    "        m = [[] for _ in range(n)]\n",
    "        for a, b, w in roads:\n",
    "            if dis[b] - dis[a] == w:\n",
    "                m[a].append(b)\n",
    "            if dis[a] - dis[b] == w:\n",
    "                m[b].append(a)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x == n - 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for y in m[x]:\n",
    "                res += dfs(y)\n",
    "            return res\n",
    "        \n",
    "        MOD = 10 ** 9 + 7\n",
    "        return dfs(0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        dist = [[float(\"inf\")] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dist[i][i] = 0\n",
    "        \n",
    "        for x, y, z in roads:\n",
    "            dist[x][y] = dist[y][x] = z\n",
    "        \n",
    "        # Floyd 算法求解最短路\n",
    "        # 完成后，dist[0][i] 即为正文部分的 dist[i]\n",
    "        # for k in range(n):\n",
    "        #     for i in range(n):\n",
    "        #         for j in range(n):\n",
    "        #             dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n",
    "\n",
    "        # Dijkstra 算法求解最短路\n",
    "        # 完成后，dist[0][i] 即为正文部分的 dist[i]\n",
    "        seen = set()\n",
    "        for _ in range(n - 1):\n",
    "            u = None\n",
    "            for i in range(n):\n",
    "                if i not in seen and (not u or dist[0][i] < dist[0][u]):\n",
    "                    u = i\n",
    "            seen.add(u)\n",
    "            for i in range(n):\n",
    "                dist[0][i] = min(dist[0][i], dist[0][u] + dist[u][i])\n",
    "\n",
    "        # 构造图 G\n",
    "        g = defaultdict(list)\n",
    "        for x, y, z in roads:\n",
    "            if dist[0][y] - dist[0][x] == z:\n",
    "                g[x].append(y)\n",
    "            elif dist[0][x] - dist[0][y] == z:\n",
    "                g[y].append(x)\n",
    "\n",
    "        @cache\n",
    "        def dfs(u: int) -> int:\n",
    "            if u == n - 1:\n",
    "                return 1\n",
    "\n",
    "            ret = 0\n",
    "            for v in g[u]:\n",
    "                ret += dfs(v)\n",
    "            return ret % mod\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        dist = [[float(\"inf\")] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dist[i][i] = 0\n",
    "        \n",
    "        for x, y, z in roads:\n",
    "            dist[x][y] = dist[y][x] = z\n",
    "        \n",
    "        # Floyd 算法求解最短路\n",
    "        # 完成后，dist[0][i] 即为正文部分的 dist[i]\n",
    "        # for k in range(n):\n",
    "        #     for i in range(n):\n",
    "        #         for j in range(n):\n",
    "        #             dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n",
    "\n",
    "        # Dijkstra 算法求解最短路\n",
    "        # 完成后，dist[0][i] 即为正文部分的 dist[i]\n",
    "        seen = set()\n",
    "        for _ in range(n - 1):\n",
    "            u = None\n",
    "            for i in range(n):\n",
    "                if i not in seen and (not u or dist[0][i] < dist[0][u]):\n",
    "                    u = i\n",
    "            seen.add(u)\n",
    "            for i in range(n):\n",
    "                dist[0][i] = min(dist[0][i], dist[0][u] + dist[u][i])\n",
    "\n",
    "        # 构造图 G\n",
    "        g = defaultdict(list)\n",
    "        for x, y, z in roads:\n",
    "            if dist[0][y] - dist[0][x] == z:\n",
    "                g[x].append(y)\n",
    "            elif dist[0][x] - dist[0][y] == z:\n",
    "                g[y].append(x)\n",
    "\n",
    "        @cache\n",
    "        def dfs(u: int) -> int:\n",
    "            if u == n - 1:\n",
    "                return 1\n",
    "\n",
    "            ret = 0\n",
    "            for v in g[u]:\n",
    "                ret += dfs(v)\n",
    "            return ret % mod\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "\n",
    "        cost = [[float('inf')] * n for _ in range(n)]\n",
    "        graph = collections.defaultdict(list)\n",
    "\n",
    "        for src, dst, time in roads:\n",
    "            graph[src].append(dst)\n",
    "            graph[dst].append(src)\n",
    "            cost[src][dst] = time\n",
    "            cost[dst][src] = time\n",
    "\n",
    "\n",
    "        minDisWay = [[float('inf'), 0] for _ in range(n)]\n",
    "        minDisWay[0] = [0, 1]\n",
    "        minHeap = [(0, 0)]\n",
    "        visited = set()\n",
    "        MOD = 10**9 + 7\n",
    "        while minHeap:\n",
    "            w, cur = heappop(minHeap)\n",
    "            if cur in visited:\n",
    "                continue;\n",
    "            visited.add(cur)\n",
    "\n",
    "            for nxt in graph[cur]:\n",
    "                nw = w + cost[cur][nxt]\n",
    "                if nw < minDisWay[nxt][0]:\n",
    "                    minDisWay[nxt] = [nw, minDisWay[cur][1]]\n",
    "                    heappush(minHeap, (nw, nxt))\n",
    "                elif nw == minDisWay[nxt][0]:\n",
    "                    minDisWay[nxt][1] = (minDisWay[nxt][1] + minDisWay[cur][1]) % MOD\n",
    "        \n",
    "        return minDisWay[n-1][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in roads:\n",
    "            graph[a].append([b, c])\n",
    "            graph[b].append([a, c])\n",
    "        dis = [float('inf')] * n \n",
    "        dis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei, cost in graph[cur]:\n",
    "                if dis[nei] > dis[cur] + cost:\n",
    "                    dis[nei] = dis[cur] + cost \n",
    "                    queue.append(nei)\n",
    "        g = collections.defaultdict(list)\n",
    "        for a, b, c in roads:\n",
    "            if dis[a] - dis[b] == c:\n",
    "                g[b].append(a)\n",
    "            if dis[b] - dis[a] == c:\n",
    "                g[a].append(b)\n",
    "        def dfs(start, memo):\n",
    "            if start == n - 1:\n",
    "                return 1\n",
    "            if start in memo:\n",
    "                return memo[start]\n",
    "            cur = 0 \n",
    "            for nei in g[start]:\n",
    "                cur += dfs(nei, memo)\n",
    "                cur %= 10 ** 9 + 7\n",
    "            memo[start] = cur\n",
    "            return cur\n",
    "        return dfs(0, {})\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: \"List[List[int]]\") -> int:\n",
    "        from collections import defaultdict\n",
    "        dct = defaultdict(set)\n",
    "        for u,v,t in roads:\n",
    "            dct[u].add((v, t))\n",
    "            dct[v].add((u, t))\n",
    "\n",
    "        res = [[float('inf'), 0] for _ in range(n)]\n",
    "        res[0] = [0, 1]\n",
    "        q = {0: [0, 1]}\n",
    "\n",
    "        while q:\n",
    "            nxt = {}\n",
    "            for u in q:\n",
    "                st, c = q[u]\n",
    "                for v, t in dct[u]:\n",
    "                    et = st + t\n",
    "                    if et > res[v][0] or et > res[-1][0]:\n",
    "                        continue\n",
    "                    elif et == res[v][0]:\n",
    "                        res[v][1] += c\n",
    "                        if v == n - 1: continue\n",
    "                        if v in nxt:\n",
    "                            nxt[v][1] += c\n",
    "                        else:\n",
    "                            nxt[v] = [et, c]\n",
    "                    else:\n",
    "                        res[v] = [et, c]\n",
    "                        if v == n - 1: continue\n",
    "                        nxt[v] = [et, c]\n",
    "\n",
    "            q = nxt\n",
    "\n",
    "        return res[-1][1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: \"List[List[int]]\") -> int:\n",
    "        from collections import defaultdict\n",
    "        dct = defaultdict(set)\n",
    "        for u,v,t in roads:\n",
    "            dct[u].add((v, t))\n",
    "            dct[v].add((u, t))\n",
    "\n",
    "        res = [[float('inf'), 0] for _ in range(n)]\n",
    "        res[0] = [0, 1]\n",
    "        q = {0: [0, 1]}\n",
    "\n",
    "        while q:\n",
    "            nxt = {}\n",
    "            for u in q:\n",
    "                st, c = q[u]\n",
    "                for v, t in dct[u]:\n",
    "                    if st + t > res[v][0] or st + t > res[-1][0]:\n",
    "                        continue\n",
    "                    elif st + t == res[v][0]:\n",
    "                        res[v][1] += c\n",
    "                        if v in nxt:\n",
    "                            nxt[v][1] += c\n",
    "                        else:\n",
    "                            nxt[v] = [st + t, c]\n",
    "                    else:\n",
    "                        res[v] = [st + t, c]\n",
    "                        nxt[v] = [st + t, c]\n",
    "\n",
    "            q = nxt\n",
    "\n",
    "        return res[-1][1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: \"List[List[int]]\") -> int:\n",
    "        from collections import defaultdict\n",
    "        dct = defaultdict(set)\n",
    "        for u,v,t in roads:\n",
    "            dct[u].add((v, t))\n",
    "            dct[v].add((u, t))\n",
    "\n",
    "        res = [[float('inf'), 0] for _ in range(n)]\n",
    "        res[0] = [0, 1]\n",
    "        q = {0: [0, 1]}\n",
    "\n",
    "        while q:\n",
    "            nxt = {}\n",
    "            for u in q:\n",
    "                st, c = q[u]\n",
    "                for v, t in dct[u]:\n",
    "                    if st + t > res[v][0] or st + t > res[-1][0]:\n",
    "                        continue\n",
    "                    elif st + t == res[v][0]:\n",
    "                        res[v][1] += c\n",
    "                        if v in nxt:\n",
    "                            nxt[v][1] += c\n",
    "                        else:\n",
    "                            nxt[v] = [st + t, c]\n",
    "                    else:\n",
    "                        res[v] = [st + t, c]\n",
    "                        nxt[v] = [st + t, c]\n",
    "\n",
    "            q = nxt\n",
    "\n",
    "        return res[-1][1] % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        dist = [[float(\"inf\")] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dist[i][i] = 0\n",
    "        \n",
    "        for x, y, z in roads:\n",
    "            dist[x][y] = dist[y][x] = z\n",
    "        \n",
    " \n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n",
    "\n",
    " \n",
    "        # 构造图 G\n",
    "        g = defaultdict(list)\n",
    "        for x, y, z in roads:\n",
    "            if dist[0][y] - dist[0][x] == z:\n",
    "                g[x].append(y)\n",
    "            elif dist[0][x] - dist[0][y] == z:\n",
    "                g[y].append(x)\n",
    "\n",
    "        @cache\n",
    "        def dfs(u: int) -> int:\n",
    "            if u == n - 1:\n",
    "                return 1\n",
    "\n",
    "            ret = 0\n",
    "            for v in g[u]:\n",
    "                ret += dfs(v)\n",
    "            return ret % mod\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mp={i:[] for i in range(n)}\n",
    "        for road in roads:\n",
    "            mp[road[0]].append((road[1],road[2]))\n",
    "            mp[road[1]].append((road[0],road[2]))  \n",
    "\n",
    "        dis=[inf]*n\n",
    "        vis=[0]*n\n",
    "        cnt=[0]*n\n",
    "\n",
    "        dis[0]=0\n",
    "        cnt[0]=1\n",
    "        heap=[(0,0)]\n",
    "\n",
    "        while heap:\n",
    "            cur=heappop(heap)\n",
    "            if vis[cur[1]]:\n",
    "                continue\n",
    "            vis[cur[1]]=1\n",
    "            for (v,w) in mp[cur[1]]:\n",
    "                #一般用Dijkstra的时候会跳过内层遍历时已确定距离的点。\n",
    "                #但由于要计算最短路数量，这里无论如何都对新确定距离的点的邻居进行全部更新。\n",
    "                if dis[v]>dis[cur[1]]+w:\n",
    "                    cnt[v]=cnt[cur[1]]\n",
    "                    dis[v]=dis[cur[1]]+w\n",
    "                    heappush(heap,(dis[v],v))\n",
    "                elif dis[v]==dis[cur[1]]+w:\n",
    "                    cnt[v]=(cnt[v]+cnt[cur[1]])%(10**9+7)\n",
    "        \n",
    "        return cnt[-1]\n",
    "\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dist = [inf] * n\n",
    "        dist[0] = 0\n",
    "        cnt = [1] + [0] * (n - 1)\n",
    "        pq = [(0, 0)]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in roads:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        st = set()\n",
    "        while pq:\n",
    "            d, u = heapq.heappop(pq)\n",
    "            if u in st:\n",
    "                continue\n",
    "            st.add(u)\n",
    "            for v, w in g[u]:\n",
    "                if dist[v] > d + w:\n",
    "                    cnt[v] = cnt[u]\n",
    "                    dist[v] = dist[u] + w\n",
    "                    heapq.heappush(pq, (dist[v], v))\n",
    "                elif dist[v] == d + w:\n",
    "                    cnt[v] = (cnt[u] + cnt[v]) % mod\n",
    "        return cnt[-1] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        mindis = [10E11]*n\n",
    "        dp = [1]+[0]*(n-1)\n",
    "        pqueue = []\n",
    "        roadgraph = [0 for _ in range(n)]\n",
    "        #构造有向图\n",
    "        for i in range(n):\n",
    "            roadgraph[i] = collections.defaultdict(int)\n",
    "        for u,v,t in roads:\n",
    "            roadgraph[u][v],roadgraph[v][u] = t,t\n",
    "        heapq.heappush(pqueue,[0,0])\n",
    "\n",
    "        #广度优先遍历有向图\n",
    "        while pqueue:\n",
    "            temp = heapq.heappop(pqueue)\n",
    "            curdis = temp[0]\n",
    "            prenode = temp[1]\n",
    "            for node,distance in roadgraph[prenode].items():\n",
    "                if (distance+curdis) < mindis[node]:\n",
    "                    heapq.heappush(pqueue,[distance+curdis,node])\n",
    "                    mindis[node] = distance+curdis\n",
    "                    dp[node] = dp[prenode]\n",
    "                elif (distance+curdis) == mindis[node]:\n",
    "                    dp[node] += dp[prenode]\n",
    "        return dp[n-1]%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        import heapq\n",
    "\n",
    "        inf = float('inf')\n",
    "        mod = 10**9+7\n",
    "        graph = defaultdict(list)\n",
    "        for x, y, cost in roads:\n",
    "            graph[x].append((y, cost))\n",
    "            graph[y].append((x, cost))\n",
    "        dist = [inf for _ in range(n)]\n",
    "        dist[0] = 0\n",
    "        p = [0 for _ in range(n)]\n",
    "        p[0] = 1\n",
    "        minHeap = []\n",
    "        heapq.heappush(minHeap, (0, 0))\n",
    "        while minHeap:\n",
    "            d, x = heapq.heappop(minHeap)\n",
    "            if d>dist[x]: continue\n",
    "            for y, cost in graph[x]:\n",
    "                if dist[x]+cost<dist[y]:\n",
    "                    dist[y] = cost+dist[x]\n",
    "                    p[y] = p[x]\n",
    "                    heapq.heappush(minHeap, (dist[y], y))\n",
    "                elif dist[x]+cost==dist[y]:\n",
    "                    p[y]+=p[x]\n",
    "        return p[-1]%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # matrix = defaultdict(dict)\n",
    "\n",
    "        # for x,y,weight in roads:\n",
    "        #     matrix[x][y]=weight\n",
    "        #     matrix[y][x]=weight\n",
    "        \n",
    "        # min_weight=2*10**13\n",
    "        # count=0\n",
    "        # visit = [0 for _ in range(n)]\n",
    "        \n",
    "        # def dfs(i,j,weight):\n",
    "        #     nonlocal min_weight,count\n",
    "        #     if visit[j]:\n",
    "        #         return\n",
    "        #     cur_weight = weight+matrix[i][j]\n",
    "        #     if j==n-1:\n",
    "                \n",
    "        #         if cur_weight<min_weight:\n",
    "        #             count=1\n",
    "        #             min_weight=cur_weight\n",
    "        #         elif cur_weight==min_weight:\n",
    "        #             count+=1\n",
    "        #         return\n",
    "            \n",
    "        #     for x in matrix[j]:\n",
    "        #         visit[j]=1\n",
    "        #         dfs(j,x,cur_weight)\n",
    "        #         visit[j]=0\n",
    "        \n",
    "        # for j in matrix[0]:\n",
    "        #     dfs(0,j,0)\n",
    "        \n",
    "        # return count\n",
    "\n",
    "        mod=1e9+7\n",
    "        matrix = defaultdict(dict)\n",
    "\n",
    "        for x,y,weight in roads:\n",
    "            matrix[x][y]=weight\n",
    "            matrix[y][x]=weight\n",
    "        \n",
    "        f = [0 for _ in range(n)]\n",
    "        f[0] = 1\n",
    "\n",
    "        queue = [(0, 0)]\n",
    "        heapify(queue)\n",
    "\n",
    "        min_dist = [1e12 for _ in range(n)]\n",
    "        visited = [0 for _ in range(n)]\n",
    "        min_dist[0]=0\n",
    "        while queue:\n",
    "            dist, node = heappop(queue)\n",
    "            # if visited[node]:\n",
    "            #     continue\n",
    "            # visited[node]=True\n",
    "            for next_node in matrix[node]:\n",
    "                cur_dist = dist + matrix[node][next_node]\n",
    "\n",
    "                if cur_dist<min_dist[next_node]:\n",
    "                    f[next_node]=f[node]\n",
    "                    min_dist[next_node]=cur_dist\n",
    "                    heappush(queue, (min_dist[next_node], next_node))\n",
    "                elif cur_dist==min_dist[next_node]:\n",
    "                    f[next_node]=(f[next_node]+f[node])%mod\n",
    "        \n",
    "        return int(f[n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        G = defaultdict(dict)\n",
    "        for a, b, s in roads:\n",
    "            G[a][b] = G[b][a] = s\n",
    "        \n",
    "        dist_list = [0] + [float('inf')] * (n - 1)\n",
    "        cnt_list = [1] + [0] * (n - 1)\n",
    "\n",
    "        heap = [(0, 0)]\n",
    "        MOD = 10 ** 9 + 7\n",
    "        while heap:\n",
    "            s, a = heappop(heap)\n",
    "            for b, ts in G[a].items():\n",
    "                if s + ts < dist_list[b]:\n",
    "                    dist_list[b] = s + ts\n",
    "                    cnt_list[b] = cnt_list[a]\n",
    "                    heappush(heap, (s + ts, b))\n",
    "                elif s + ts == dist_list[b]:\n",
    "                    cnt_list[b] = (cnt_list[b] + cnt_list[a]) % MOD\n",
    "\n",
    "        return cnt_list[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        adj = defaultdict(list)\n",
    "        for s, d, t in roads:\n",
    "            adj[s].append((d, t))\n",
    "            adj[d].append((s, t))\n",
    "\n",
    "        h = []\n",
    "        heapq.heappush(h, (0, 0))\n",
    "        dist = [float('inf')] * n\n",
    "        dist[0] = 0\n",
    "        while h:\n",
    "            d, cur = heapq.heappop(h)\n",
    "            if d > dist[cur]:\n",
    "                continue\n",
    "            dist[cur] = d\n",
    "            for neighbor, t in adj[cur]:\n",
    "                if d + t < dist[neighbor]:\n",
    "                    dist[neighbor] = d + t\n",
    "                    heapq.heappush(h, (d + t, neighbor))\n",
    "        budget = dist[n - 1]\n",
    "        visited = set()\n",
    "        total = [budget]\n",
    "        @cache\n",
    "        def dfs(x, budget, dest):\n",
    "            if x == dest:\n",
    "                if budget == 0:\n",
    "                    return 1\n",
    "            if budget < 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for neighbor, t in adj[x]:\n",
    "                if neighbor not in visited and total[0] - budget + t <= dist[neighbor]:\n",
    "                    visited.add(neighbor)\n",
    "                    res += dfs(neighbor, budget - t, dest)\n",
    "                    visited.remove(neighbor)\n",
    "            return res\n",
    "        return dfs(0, budget, n - 1) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        dp = dict()\n",
    "        for start,end,time in roads:\n",
    "            dp[start] = dp.get(start,[])+[(end,time)]\n",
    "            dp[end] = dp.get(end,[])+[(start,time)]\n",
    "\n",
    "        paths = [[] for _ in range(n)]\n",
    "        # val,num\n",
    "        paths[0] = [0,1]\n",
    "        # value,idx\n",
    "        queue = [(0,0)]\n",
    "        heapq.heapify(queue)\n",
    "        vised = set()\n",
    "        while queue:\n",
    "            v,start = heapq.heappop(queue)\n",
    "            if start in vised:\n",
    "                continue\n",
    "            for end,time in dp[start]:\n",
    "                if paths[end]:\n",
    "                    if paths[end][0]>paths[start][0]+time:\n",
    "                        paths[end][0] = paths[start][0]+time\n",
    "                        paths[end][1] = paths[start][1]\n",
    "                    elif paths[end][0]==paths[start][0]+time:\n",
    "                        paths[end][1]+=paths[start][1]\n",
    "                else:\n",
    "                    paths[end] = [paths[start][0]+time,paths[start][1]]\n",
    "                    \n",
    "                heapq.heappush(queue,(paths[end][0],end))\n",
    "                vised.add(start)\n",
    "        return paths[-1][-1] % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        heap, MOD = [(0, 0)], 10 ** 9 + 7\n",
    "        edges = collections.defaultdict(list)\n",
    "        for u, v, t in roads:\n",
    "            edges[u].append((v, t))\n",
    "            edges[v].append((u, t))\n",
    "\n",
    "        # 记录从0节点到每个节点的最短路长\n",
    "        min_cost = [math.inf] * n\n",
    "        while heap:\n",
    "            cost, cur_node = heapq.heappop(heap)\n",
    "            # 一旦当前的cost已经>=到达cur_node的最短路长，说明cur_node已经访问过了，可以跳过，\n",
    "            # 这里需要注意的是用的是>=符号，而不是>符号，否则会重复考察cur_node点\n",
    "            if cost >= min_cost[cur_node]:\n",
    "                continue\n",
    "            if cur_node == n - 1:\n",
    "                min_cost[-1] = cost\n",
    "                break\n",
    "            min_cost[cur_node] = cost\n",
    "            for (nxt_node, time) in edges[cur_node]:\n",
    "                if cost + time <= min_cost[nxt_node]:\n",
    "                    heapq.heappush(heap, (cost + time, nxt_node))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur_node: int, step: int) -> int:\n",
    "            if step == min_cost[-1]:\n",
    "                if cur_node == n - 1:\n",
    "                    return 1\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            for (nxt_node, time) in edges[cur_node]:\n",
    "                # 要从0节点以最短路长走到n-1节点，必然到每个途径节点也是最短路长，\n",
    "                # 所以只有满足到下个节点是最短路长的时候，才考虑这条路径\n",
    "                if step + time == min_cost[nxt_node]:\n",
    "                    res += dfs(nxt_node, step + time)\n",
    "            return res % MOD\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        heap, MOD = [(0, 0)], 10 ** 9 + 7\n",
    "        edges = collections.defaultdict(list)\n",
    "        for u, v, t in roads:\n",
    "            edges[u].append((v, t))\n",
    "            edges[v].append((u, t))\n",
    "\n",
    "        # 记录从0节点到每个节点的最短路长\n",
    "        min_cost = [math.inf] * n\n",
    "        while heap:\n",
    "            cost, cur_node = heapq.heappop(heap)\n",
    "            # 一旦当前的cost已经>=到达cur_node的最短路长，说明cur_node已经访问过了，可以跳过，\n",
    "            # 这里需要注意的是用的是>=符号，而不是>符号，否则会重复考察cur_node点\n",
    "            if cost >= min_cost[cur_node]:\n",
    "                continue\n",
    "            if cur_node == n - 1:\n",
    "                min_cost[-1] = cost\n",
    "                break\n",
    "            min_cost[cur_node] = cost\n",
    "            for (nxt_node, time) in edges[cur_node]:\n",
    "                if cost + time <= min_cost[nxt_node]:\n",
    "                    heapq.heappush(heap, (cost + time, nxt_node))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur_node: int, step: int) -> int:\n",
    "            if step > min_cost[-1]:\n",
    "                return 0\n",
    "            if step == min_cost[-1]:\n",
    "                if cur_node == n - 1:\n",
    "                    return 1\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            for (nxt_node, time) in edges[cur_node]:\n",
    "                # 要从0节点以最短路长走到n-1节点，必然到每个途径节点也是最短路长，\n",
    "                # 所以只有满足到下个节点是最短路长的时候，才考虑这条路径\n",
    "                if step + time == min_cost[nxt_node]:\n",
    "                    res += dfs(nxt_node, step + time)\n",
    "            return res % MOD\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dp = [[-1]*n for i in range(n)]\n",
    "        g = defaultdict(lambda: defaultdict(int))\n",
    "        for u, v, w in roads:\n",
    "            dp[u][v] = w\n",
    "            dp[v][u] = w\n",
    "            g[u][v] = w\n",
    "            g[v][u] = w\n",
    "\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                if dp[i][k]==-1: continue\n",
    "                for j in range(n):\n",
    "                    if dp[k][j]==-1: continue\n",
    "                    if -1==dp[i][j] or dp[i][j]>dp[i][k]+dp[k][j]:\n",
    "                        dp[i][j] = dp[i][k]+dp[k][j]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "            \n",
    "        @cache\n",
    "        def h(i):\n",
    "            # i~n-1 的方案数\n",
    "            if i==n-1: return 1\n",
    "            res = 0\n",
    "            for j in g[i]:\n",
    "                if g[i][j]+dp[j][n-1]==dp[i][n-1]:\n",
    "                    res += h(j)\n",
    "            return res % 1_000_000_007\n",
    "\n",
    "        return h(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in roads:\n",
    "            graph[a].append([b, c])\n",
    "            graph[b].append([a, c])\n",
    "        dis = [float('inf')] * n \n",
    "        dis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei, cost in graph[cur]:\n",
    "                if dis[nei] > dis[cur] + cost:\n",
    "                    dis[nei] = dis[cur] + cost \n",
    "                    queue.append(nei)\n",
    "        G = collections.defaultdict(list)\n",
    "        for a, b, c in roads:\n",
    "            if dis[a] - dis[b] == c:\n",
    "                G[b].append(a)\n",
    "            if dis[b] - dis[a] == c:\n",
    "                G[a].append(b)\n",
    "        @lru_cache(None)\n",
    "        def dfs(start):\n",
    "            if start == n - 1:\n",
    "                return 1 \n",
    "            s = 0\n",
    "            for nei in G[start]:\n",
    "                s += dfs(nei)\n",
    "            return s \n",
    "        return dfs(0) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef countPaths(self, n, roads):\n",
    "\t\tbase = 10 ** 9 + 7\n",
    "\t\tmap0 = {i: [] for i in range(n)}\n",
    "\t\tfor u, v, t in roads:\n",
    "\t\t\tmap0[u].append([v, t])\n",
    "\t\t\tmap0[v].append([u, t])\n",
    "\t\tmap1 = {i: [float('inf'), 0, i] for i in range(n)}\n",
    "\t\tmap1[n - 1] = [0, 1, n - 1]\n",
    "\t\tq = [map1[n - 1]]\n",
    "\t\tpool = {n - 1}\n",
    "\t\twhile q:\n",
    "\t\t\td, cnt, cur = heapq.heappop(q)\n",
    "\t\t\tpool.remove(cur)\n",
    "\t\t\tfor v, t in map0[cur]:\n",
    "\t\t\t\tif d + t > map1.get(v, [float('inf'), 0])[0]:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tif d + t == map1.get(v, [float('inf'), 0])[0]:\n",
    "\t\t\t\t\tmap1[v][1] += map1[cur][1]\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tmap1[v][0] = d + t\n",
    "\t\t\t\t\tmap1[v][1] = cnt\n",
    "\t\t\t\tif v not in pool:\n",
    "\t\t\t\t\theapq.heappush(q, map1[v])\n",
    "\t\t\t\t\tpool.add(v)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\theapq.heapify(q)\n",
    "\t\treturn map1[0][1] % base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def dijkstra(self,n,roads):\n",
    "    #     graph=defaultdict(list)\n",
    "    #     for link in roads:\n",
    "    #         x,y,d=roads\n",
    "    #         graph[x].append((y,d))\n",
    "    #         graph[y].append((x,d))\n",
    "    #     que=[(0,0)]#(dist,source)\n",
    "    #     dist=[float('inf')]*n\n",
    "    #     while que:\n",
    "    #         d,cur=heapq.heappop(que)\n",
    "    #         if d>dist[cur]:\n",
    "    #             continue\n",
    "    #         for point,d1 in graph[cur]:\n",
    "    #             if d1>0 and dist[cur]+d1<dist[point]:\n",
    "    #                 dist[point]=dist[cur]+d1\n",
    "    #                 heapq.heappush(que,(dist[point],point))\n",
    "    #     return dist\n",
    "\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, time in roads:\n",
    "            graph[u].append((v, time))\n",
    "            graph[v].append((u, time))\n",
    "        \n",
    "        distances = [float('inf')] * n\n",
    "        path_counts = [0] * n\n",
    "        \n",
    "        distances[0] = 0\n",
    "        path_counts[0] = 1\n",
    "        \n",
    "        heap = [(0, 0)]  # 优先队列，存储距离和节点元组\n",
    "        \n",
    "        while heap:\n",
    "            dist, node = heapq.heappop(heap)\n",
    "            \n",
    "            if dist > distances[node]:\n",
    "                continue\n",
    "            \n",
    "            for neighbor, time in graph[node]:\n",
    "                if dist + time < distances[neighbor]:\n",
    "                    distances[neighbor] = dist + time\n",
    "                    path_counts[neighbor] = path_counts[node]\n",
    "                    heapq.heappush(heap, (dist + time, neighbor))\n",
    "                elif dist + time == distances[neighbor]:\n",
    "                    path_counts[neighbor] = (path_counts[neighbor] + path_counts[node]) % MOD\n",
    "        \n",
    "        return path_counts[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        #堆优化的迪杰斯特拉算法+路径计数DP\n",
    "        graph=defaultdict(list)\n",
    "        for u,v,time in roads:\n",
    "            graph[u].append((v,time))\n",
    "            graph[v].append((u,time))\n",
    "        dis=[inf]*n\n",
    "        dis[0]=0\n",
    "        #f[i]表示0到i的最短路径数量\n",
    "        f=[0]*n\n",
    "        f[0]=1\n",
    "        h=[(0,0)]\n",
    "        heapq.heapify(h)\n",
    "        while h:\n",
    "            curdis,x=heapq.heappop(h)\n",
    "            if curdis>dis[x]:\n",
    "                continue\n",
    "            for y,cost in graph[x]:\n",
    "                if dis[x]+cost<dis[y]:\n",
    "                    dis[y]=dis[x]+cost\n",
    "                    f[y]=f[x]\n",
    "                    heapq.heappush(h,(dis[y],y))\n",
    "                elif dis[x]+cost==dis[y]:\n",
    "                    f[y]+=f[x]\n",
    "        return f[n-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        mod = int(1e9+7)\n",
    "        for u,v,time in roads:\n",
    "            g[u].append((v,time))\n",
    "            g[v].append((u,time))\n",
    "        dist = [inf] * n    # time\n",
    "        cnt = [0] * n       # 最短时间为time时对应的路径数量\n",
    "        dist[0] = 0\n",
    "        cnt[0] = 1\n",
    "        # (time, node)\n",
    "        pq = [(0,0)]\n",
    "        while pq:\n",
    "            last_time, u = heappop(pq)\n",
    "            for v,time in g[u]:\n",
    "                if dist[v] > last_time + time:\n",
    "                    dist[v] = last_time + time\n",
    "                    heappush(pq,(dist[v], v))\n",
    "                    cnt[v] = cnt[u]\n",
    "                # 时间相同\n",
    "                elif dist[v] == last_time + time:\n",
    "                    cnt[v] += cnt[u]\n",
    "        return cnt[-1] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, w in roads:\n",
    "            graph[u].append((v, w))\n",
    "            graph[v].append((u, w))\n",
    "\n",
    "        heap = [(0, 0)]\n",
    "        dist, cnter = [math.inf] * n, [0] * n\n",
    "        dist[0] = 0\n",
    "        cnter[0] = 1\n",
    "        while heap:\n",
    "            d, cur = heapq.heappop(heap)\n",
    "            if d > dist[cur]:\n",
    "                continue\n",
    "            for nxt, w in graph[cur]:\n",
    "                if d + w == dist[nxt]:\n",
    "                    cnter[nxt] += cnter[cur] \n",
    "                    cnter[nxt] %= MOD\n",
    "                elif d + w < dist[nxt]:\n",
    "                    dist[nxt] = d + w\n",
    "                    cnter[nxt] = cnter[cur] \n",
    "                    heapq.heappush(heap, (d + w, nxt))\n",
    "        return cnter[-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from heapq import heappop\n",
    "from heapq import heappush\n",
    "from math import inf\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for u, v, t in roads:\n",
    "            g[u].append((v, t))\n",
    "            g[v].append((u, t))\n",
    "\n",
    "        def dijkstra() -> List[int]:\n",
    "            dist = [inf] * n\n",
    "            q = [(0, 0)]\n",
    "            dist[0] = 0\n",
    "            while q:\n",
    "                d, x = heappop(q)\n",
    "                if d > dist[x]:\n",
    "                    continue\n",
    "                for y, t in g[x]:\n",
    "                    if dist[x] + t < dist[y]:\n",
    "                        dist[y] = dist[x] + t\n",
    "                        heappush(q, (dist[y], y))\n",
    "            return dist\n",
    "        #最短路径\n",
    "        dist = dijkstra()\n",
    "        # 重建DAG图\n",
    "        dag = [[] for _ in range(n)]\n",
    "        # 入度\n",
    "        edg = [0] * n\n",
    "        for u, v, t in roads:\n",
    "            # u到v是在最短路径上的\n",
    "            if dist[u] + t == dist[v]:\n",
    "                dag[u].append(v)\n",
    "                edg[v] += 1\n",
    "            elif dist[v] + t == dist[u]:\n",
    "                dag[v].append(u)\n",
    "                edg[u] += 1\n",
    "\n",
    "        # 拓扑排序DP\n",
    "        # 定义f[i]为到节点i的最短路径数量\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        q = deque()\n",
    "        #入度为0的进入队列，这里只有节点0，其它的入度为0的节点都被重建dag的过程排除了\n",
    "        q.append(0)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in dag[x]:\n",
    "                f[y] += f[x]\n",
    "                f[y] %= MOD\n",
    "                edg[y] -= 1\n",
    "                if edg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        mod = int(1e9+7)\n",
    "        for u,v,time in roads:\n",
    "            g[u].append((v,time))\n",
    "            g[v].append((u,time))\n",
    "        dist = [inf] * n\n",
    "        # time\n",
    "        dist[0] = 0\n",
    "        cnt = [0] * n\n",
    "        cnt[0] = 1\n",
    "        pq = PriorityQueue()\n",
    "        pq.put((0,0))\n",
    "        while not pq.empty():\n",
    "            last_time, u = pq.get()\n",
    "            for v,time in g[u]:\n",
    "                if dist[v] > last_time + time:\n",
    "                    dist[v] = last_time + time\n",
    "                    pq.put((dist[v], v))\n",
    "                    cnt[v] = cnt[u]\n",
    "                elif dist[v] == last_time + time:\n",
    "                    cnt[v] += cnt[u]\n",
    "        \n",
    "        return cnt[-1] % mod\n",
    "s = Solution()\n",
    "s.countPaths(7,[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]])\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10**9+7\n",
    "        edges = defaultdict(list)\n",
    "        for u,v,w in roads:\n",
    "            edges[u].append((v,w))\n",
    "            edges[v].append((u,w))\n",
    "        dis = [inf]*n\n",
    "        dis[0] = 0\n",
    "        q = [(0,0)]\n",
    "        vis = set()\n",
    "        while q:\n",
    "            d,u = heapq.heappop(q)\n",
    "            vis.add(u)\n",
    "            for v,w in edges[u]:\n",
    "                if v not in vis and w+d < dis[v]:\n",
    "                    dis[v] = w+d\n",
    "                    heapq.heappush(q, (dis[v], v))\n",
    "        g = defaultdict(list)\n",
    "        for u,v,w in roads:\n",
    "            if dis[u]-dis[v] == w:\n",
    "                g[v].append(u)\n",
    "            elif dis[v]-dis[u] == w:\n",
    "                g[u].append(v)\n",
    "        @cache\n",
    "        def dfs(u):\n",
    "            if u == n-1:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for v in g[u]:\n",
    "                ans = (ans+dfs(v))%mod\n",
    "            return ans\n",
    "        ans = dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        #dijk算法 或者拓扑排序\n",
    "        # 路径数目\n",
    "        # 2个数组，一个记录最小值，一个记录次数\n",
    "        MOD = 10**9+7\n",
    "        dist_to =[ [inf,0] for _ in range(n) ]\n",
    "        dist_to[0][0] = 0\n",
    "        dist_to[0][1] = 1 #直接可以到达0\n",
    "        g = defaultdict(list)\n",
    "        for x,y,w in roads:\n",
    "            g[x].append((y,w))\n",
    "            g[y].append((x,w))\n",
    "        hq = []\n",
    "        heapq.heappush(hq,(0,0))\n",
    "        while hq:\n",
    "            w,x = heapq.heappop(hq)            \n",
    "            if w > dist_to[x][0]:\n",
    "                continue\n",
    "            for y,w2 in g[x]:\n",
    "                d = dist_to[x][0] + w2\n",
    "                if d < dist_to[y][0]:\n",
    "                    dist_to[y][0] = d\n",
    "                    dist_to[y][1] = dist_to[x][1] #置为x对应的DP值\n",
    "                    heapq.heappush(hq,(d,y))\n",
    "\n",
    "                elif d == dist_to[y][0]:#遇到相同最小的结果，直接相加\n",
    "                    dist_to[y][1] += dist_to[x][1]\n",
    "                    # 不再加入堆中\n",
    "\n",
    "        return dist_to[-1][1]%MOD\n",
    "\n",
    "                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = [[] for i in range(n)]\n",
    "        for edge in roads:\n",
    "            graph[edge[0]].append((edge[1], edge[2]))\n",
    "            graph[edge[1]].append((edge[0], edge[2]))\n",
    "        def dijkstra(startnode, n):\n",
    "            q = []\n",
    "            distances = [inf for i in range(n)]\n",
    "            distances[startnode] = 0\n",
    "            heapq.heappush(q, (0, startnode))\n",
    "            while len(q) != 0:\n",
    "                temp = heapq.heappop(q)\n",
    "                if temp[0] > distances[temp[1]]:\n",
    "                    continue\n",
    "                for nextnode in graph[temp[1]]:\n",
    "                    distance = temp[0] + nextnode[1]\n",
    "                    if distance < distances[nextnode[0]]:\n",
    "                        distances[nextnode[0]] = distance\n",
    "                        heapq.heappush(q, (distance, nextnode[0]))\n",
    "            return distances\n",
    "        distances = dijkstra(0, n)\n",
    "        print(distances)\n",
    "        g = defaultdict(list)\n",
    "        for x, y, z in roads:\n",
    "            if distances[y] - distances[x] == z:\n",
    "                g[x].append(y)\n",
    "            elif distances[x] - distances[y] == z:\n",
    "                g[y].append(x)\n",
    "        @cache\n",
    "        def dfs(u):\n",
    "            if u == n - 1:\n",
    "                return 1\n",
    "            ret = 0\n",
    "            for v in g[u]:\n",
    "                ret += dfs(v)\n",
    "            return ret % (10**9 + 7)\n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPaths1(self, n: int, roads: list[list[int]]) -> int:\n",
    "        in_degrees = [0] * n\n",
    "        dic = collections.defaultdict(list)\n",
    "        dic_val = collections.defaultdict()\n",
    "        for road in roads:\n",
    "            if road[1] < road[0]:\n",
    "                road[1], road[0] = road[0], road[1]\n",
    "            in_degrees[road[1]] += 1\n",
    "            dic[road[0]].append(road[1])\n",
    "            dic_val[(road[0], road[1])] = road[2]\n",
    "        print(in_degrees)\n",
    "        print(dic)\n",
    "        print(dic_val)\n",
    "        cur_level = {0}\n",
    "        # visited.add(0)\n",
    "        path_dict = collections.defaultdict(set)\n",
    "        while cur_level:\n",
    "            next_level = collections.defaultdict(set)\n",
    "            for node in cur_level:\n",
    "                for v in dic[node]:\n",
    "                    next_level[v].add(node)\n",
    "                print(\"next_level\", next_level)\n",
    "            cur_level = next_level\n",
    "            path_dict.update(next_level)\n",
    "            print(path_dict)\n",
    "\n",
    "        rst = [[6]]\n",
    "        while rst and rst[0][0] != 0:\n",
    "            rst = [[p] + r for r in rst for p in path_dict[r[0]]]\n",
    "        print(rst)\n",
    "        return 0\n",
    "\n",
    "    def countPaths2(self, n: int, roads: list[list[int]]) -> int:\n",
    "        rd = collections.defaultdict(lambda: collections.defaultdict(int))\n",
    "        print(rd)\n",
    "        for a, b, t in roads:\n",
    "            rd[a][b] = rd[b][a] = t\n",
    "        print(rd)\n",
    "        q, min_t = [(0, 0)], [0] + [float('inf')] * (n - 1)\n",
    "        while q:\n",
    "            t, nd = heapq.heappop(q)\n",
    "            for next_nd in rd[nd]:\n",
    "                if t + rd[nd][next_nd] >= min_t[next_nd]:\n",
    "                    continue\n",
    "                min_t[next_nd] = t + rd[nd][next_nd]\n",
    "                heapq.heappush(q, (min_t[next_nd], next_nd))\n",
    "                print(q)\n",
    "        print(rd)\n",
    "        print(q)\n",
    "        print(heapq)\n",
    "        dfs = cache(lambda nd: 1 if nd == n - 1 else sum(\n",
    "            dfs(next_nd) for next_nd in rd[nd] if rd[nd][next_nd] == min_t[next_nd] - min_t[nd]) % 1000000007)\n",
    "        return dfs(0)\n",
    "\n",
    "    def countPaths(self, n: int, roads: list[list[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        dct = defaultdict(set)\n",
    "        for u, road_to, road_weight in roads:\n",
    "            dct[u].add((road_to, road_weight))\n",
    "            dct[road_to].add((u, road_weight))\n",
    "\n",
    "        print(dct)\n",
    "\n",
    "        res = [[float('inf'), 0] for _ in range(n)]\n",
    "        res[0] = [0, 1]\n",
    "        q = {0: [0, 1]}\n",
    "\n",
    "        while q:\n",
    "            nxt = {}\n",
    "            for road_in in q:\n",
    "                cur_sum_weight, cur_road_num = q[road_in]\n",
    "                for road_to, road_weight in dct[road_in]:\n",
    "                    if cur_sum_weight + road_weight > res[road_to][0] or cur_sum_weight + road_weight > res[-1][0]:\n",
    "                        continue\n",
    "                    elif cur_sum_weight + road_weight == res[road_to][0]:\n",
    "                        res[road_to][1] += cur_road_num\n",
    "                        if road_to in nxt:\n",
    "                            nxt[road_to][1] += cur_road_num\n",
    "                        elif road_to != n - 1:\n",
    "                            # else:\n",
    "                            nxt[road_to] = [cur_sum_weight + road_weight, cur_road_num]\n",
    "                    else:\n",
    "                        res[road_to] = [cur_sum_weight + road_weight, cur_road_num]\n",
    "                        nxt[road_to] = [cur_sum_weight + road_weight, cur_road_num]\n",
    "\n",
    "            q = nxt\n",
    "\n",
    "        return res[-1][1] % 1000000007\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solution = Solution()\n",
    "    n = 7\n",
    "    roads = [[0, 6, 7], [0, 1, 2], [1, 2, 3], [1, 3, 3], [6, 3, 3], [3, 5, 1], [6, 5, 1], [2, 5, 1], [0, 4, 5],\n",
    "             [4, 6, 2]]\n",
    "    res = solution.countPaths(n, roads)\n",
    "    print(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v, time in roads:\n",
    "            graph[u].append([v, time])\n",
    "            graph[v].append([u, time])\n",
    "\n",
    "        def dijkstra(src):\n",
    "            dist = [math.inf] * n\n",
    "            ways = [0] * n\n",
    "            minHeap = [(0, src)]  # dist, src\n",
    "            dist[src] = 0\n",
    "            ways[src] = 1\n",
    "            while minHeap:\n",
    "                d, u = heappop(minHeap)\n",
    "                if dist[u] < d: continue  # Skip if `d` is not updated to latest version!\n",
    "                for v, time in graph[u]:\n",
    "                    if dist[v] > d + time:\n",
    "                        dist[v] = d + time\n",
    "                        ways[v] = ways[u]\n",
    "                        heappush(minHeap, (dist[v], v))\n",
    "                    elif dist[v] == d + time:\n",
    "                        ways[v] = (ways[v] + ways[u]) % 1_000_000_007\n",
    "            return ways[n - 1]\n",
    "\n",
    "        return dijkstra(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j, c in roads:\n",
    "            dct[i].append([j, c])\n",
    "            dct[j].append([i, c])\n",
    "        \n",
    "        src = 0\n",
    "        mod = 10**9 + 7\n",
    "        n = len(dct)\n",
    "        dis = [inf] * n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "        cnt = [0] * n\n",
    "        cnt[src] = 1\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    # 最短距离更新，重置计数\n",
    "                    cnt[j] = cnt[i]\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "                elif dj == dis[j]:\n",
    "                    # 最短距离一致，增加计数\n",
    "                    cnt[j] += cnt[i]\n",
    "                    cnt[j] %= mod\n",
    "        return cnt[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y,z in roads:\n",
    "            g[x].append([y,z])\n",
    "            g[y].append([x,z])\n",
    "        dis = [inf] * n\n",
    "        path = [0] * n\n",
    "        path[0] = 1\n",
    "        dis[0] = 0\n",
    "        pq = [(0, 0)]\n",
    "        while pq:\n",
    "            t0, u = heappop(pq)\n",
    "            for v, t1 in g[u]:\n",
    "                new_d = t0 + t1\n",
    "                if new_d < dis[v]:\n",
    "                    path[v] = path[u]\n",
    "                    dis[v] = new_d\n",
    "                    heappush(pq, (new_d, v))\n",
    "                elif new_d == dis[v]:\n",
    "                    path[v] += path[u]\n",
    "                    path[v] %= 1000000007\n",
    "        return path[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        graph=defaultdict(list)\n",
    "        for e in roads:\n",
    "            graph[e[0]].append([e[1],e[2]])\n",
    "            graph[e[1]].append([e[0],e[2]])\n",
    "\n",
    "        visited=set()\n",
    "        distance=[[float('inf'),0] if i!=0 else [0,1] for i in range(n)]  #distance[i][0]表示0点到i点的最短距离，distance[i][1]表示0点到i点最短距离的方案数\n",
    "\n",
    "        from heapq import heappush,heappop\n",
    "        heap=[[0,0,0]]  #heap[i][0]表示0点到heap[i][1]点的当前距离，heap[i][1]是目的地节点，heap[i][2]表示目的地节点的父节点\n",
    "        while heap:\n",
    "            node=heappop(heap)\n",
    "            if node[1] not in visited:\n",
    "                visited.add(node[1])\n",
    "                distance[node[1]][0]=node[0]\n",
    "                distance[node[1]][1]=distance[node[2]][1]\n",
    "                for m in graph[node[1]]: \n",
    "                    if m[0] not in visited: heappush(heap,[node[0]+m[1],m[0],node[1]])\n",
    "            else:\n",
    "                if distance[node[1]][0]==node[0]: distance[node[1]][1]=(distance[node[1]][1]+distance[node[2]][1])%1000000007\n",
    "\n",
    "        return distance[-1][1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a,b,w in roads:\n",
    "            g[a].append([b,w])\n",
    "            g[b].append([a,w])\n",
    "        q = []\n",
    "        dist = [0x3f3f3f3f3f] * n\n",
    "        pre = [[] for _ in range(n)]\n",
    "        dist[0] = 0\n",
    "        heapq.heappush(q,(0,0))\n",
    "      \n",
    "        while len(q) > 0:\n",
    "            d,cur = heapq.heappop(q)\n",
    "        \n",
    "            for nei,di in g[cur]:\n",
    "                if dist[nei] > dist[cur] + di:\n",
    "                    dist[nei] = dist[cur] + di\n",
    "                    heapq.heappush(q,(dist[nei],nei))\n",
    "        inc = [0] * n  \n",
    "\n",
    "        g1 = defaultdict(list)\n",
    "        dp = [0] * n\n",
    "        for a,b,w in roads:\n",
    "            if dist[a] == dist[b] + w:\n",
    "                inc[a] += 1\n",
    "                g1[b].append(a)\n",
    "            if dist[b] == dist[a] + w:\n",
    "                inc[b] += 1\n",
    "                g1[a].append(b)\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if inc[i] == 0:\n",
    "                q.append(i)\n",
    "        mod = pow(10,9) + 7\n",
    "        dp[0] = 1\n",
    "        while len(q):\n",
    "            cur = q.popleft()\n",
    "            for nei in g1[cur]:\n",
    "                inc[nei] -= 1\n",
    "                dp[nei] += dp[cur]\n",
    "                dp[nei] = dp[nei] % mod\n",
    "                if inc[nei] == 0:\n",
    "                    q.append(nei)\n",
    "      \n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, t in roads:\n",
    "            graph[u].append([v, t])\n",
    "            graph[v].append([u, t])\n",
    "        dis = [float('inf')] * n \n",
    "        dis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei, cost in graph[cur]:\n",
    "                if dis[nei] > dis[cur] + cost:\n",
    "                    dis[nei] = dis[cur] + cost\n",
    "                    queue.append(nei)\n",
    "        g = collections.defaultdict(list)\n",
    "        for u, v, t in roads:\n",
    "            if dis[u] - dis[v] == t:\n",
    "                g[v].append(u)\n",
    "            if dis[v] - dis[u] == t:\n",
    "                g[u].append(v)\n",
    "        @lru_cache(None)\n",
    "        def dfs(start):\n",
    "            if start == n - 1:\n",
    "                return 1 \n",
    "            res = 0\n",
    "            for nei in g[start]:\n",
    "                res += dfs(nei)\n",
    "                res %= 10 ** 9 + 7\n",
    "            return res \n",
    "        return dfs(0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for u,v,t in roads:\n",
    "            g[u].append([v,t])\n",
    "            g[v].append([u,t])\n",
    "        dis=[inf for _ in range(n)]\n",
    "        cnt=[0]*n\n",
    "        cnt[0]=1\n",
    "        dis[0]=0\n",
    "        q=[[0,0]]\n",
    "        vis=[[False]*n for _ in range(n)]\n",
    "        while q:\n",
    "            dd,e=heapq.heappop(q)\n",
    "            for nei,d in g[e]:\n",
    "                if not vis[e][nei]:\n",
    "                    if dis[nei]>dis[e]+d:\n",
    "                        dis[nei]=d+dis[e]\n",
    "                        cnt[nei]=cnt[e]\n",
    "                        heapq.heappush(q, [dis[nei],nei])\n",
    "                    elif dis[nei]==d+dis[e]:\n",
    "                        if nei==n-1:\n",
    "                            print(e,cnt[e])\n",
    "                        cnt[nei]+=cnt[e]\n",
    "                        heapq.heappush(q, [dis[nei],nei])\n",
    "                vis[e][nei]=True\n",
    "        #print(cnt)\n",
    "        #print(dis)\n",
    "        return cnt[n-1]%(10**9+7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for u,v,t in roads:\n",
    "            g[u].append([v,t])\n",
    "            g[v].append([u,t])\n",
    "        dis=[inf for _ in range(n)]\n",
    "        cnt=[0]*n\n",
    "        cnt[0]=1\n",
    "        dis[0]=0\n",
    "        q=[[0,0]]\n",
    "        vis=[[False]*n for _ in range(n)]\n",
    "        while q:\n",
    "            dd,e=heapq.heappop(q)\n",
    "            for nei,d in g[e]:\n",
    "                if not vis[e][nei]:\n",
    "                    if dis[nei]>dis[e]+d:\n",
    "                        dis[nei]=d+dis[e]\n",
    "                        cnt[nei]=cnt[e]\n",
    "                        heapq.heappush(q, [dis[nei],nei])\n",
    "                    elif dis[nei]==d+dis[e]:\n",
    "                        cnt[nei]+=cnt[e]\n",
    "                        heapq.heappush(q, [dis[nei],nei])\n",
    "                vis[e][nei]=True\n",
    "        #print(cnt)\n",
    "        #print(dis)\n",
    "        return cnt[n-1]%(10**9+7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        MOD = 10 ** 9 + 7\n",
    "        routes = {}\n",
    "        for road in roads:\n",
    "            routes.setdefault(road[0], set()).add((road[1], road[2]))\n",
    "            routes.setdefault(road[1], set()).add((road[0], road[2]))\n",
    "        point_min = {0: 0, n - 1: sys.maxsize}\n",
    "        res = 0\n",
    "        current = {0: [0, 1]}  # 点位: [时间， 到达次数]\n",
    "        while current:\n",
    "            next_points = {}\n",
    "            for p, (t, count) in current.items():\n",
    "                for next_p, next_t in routes[p]:\n",
    "                    nt = t + next_t\n",
    "                    if next_p == n - 1:\n",
    "                        if nt == point_min[n - 1]:\n",
    "                            res += count\n",
    "                            res %= MOD\n",
    "                        elif nt < point_min[n - 1]:\n",
    "                            res = count\n",
    "                            point_min[n - 1] = nt\n",
    "                    elif next_p in point_min and nt > point_min[next_p]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        point_min[next_p] = nt\n",
    "                        if next_p not in next_points or next_points[next_p][0] > nt:\n",
    "                            next_points[next_p] = [nt, count]\n",
    "                        elif next_points[next_p][0] == nt:\n",
    "                            next_points[next_p][1] += count\n",
    "            current = next_points\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dist = [float('inf')] * n\n",
    "        dist[0] = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for x, y, z in roads:\n",
    "            g[x].append((y, z))\n",
    "            g[y].append((x, z))\n",
    "\n",
    "\n",
    "        seen = set()\n",
    "        for _ in range(n-1):\n",
    "            u = None\n",
    "            for x in range(n):\n",
    "                if x not in seen and (u is None or dist[x] < dist[u]):\n",
    "                    u = x\n",
    "\n",
    "            seen.add(u)\n",
    "            for x, z in g[u]:\n",
    "                dist[x] = min(dist[x], dist[u] + z)\n",
    "             \n",
    "        # print(dist)\n",
    "\n",
    "        G = defaultdict(list)\n",
    "        for x, y, z in roads:\n",
    "            if dist[x] - dist[y] == z:\n",
    "                G[y].append((x, z))\n",
    "            if dist[y] - dist[x] == z:\n",
    "                G[x].append((y, z))\n",
    "        @cache\n",
    "        def dfs(v):\n",
    "            if v == n-1:\n",
    "                return 1\n",
    "            ret = 0\n",
    "            for next_v, z in G[v]:\n",
    "                ret += dfs(next_v)\n",
    "            return ret % mod\n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "def dijkstra(graph, cost, start):\n",
    "    n = len(graph)\n",
    "    dis = [inf] * n\n",
    "    dis[start] = 0\n",
    "    q = [(0, start)]\n",
    "\n",
    "    while q:\n",
    "        d, node = heapq.heappop(q)\n",
    "        if d > dis[node]:\n",
    "            continue\n",
    "\n",
    "        for ch in graph[node]:\n",
    "            if d + cost[node][ch] < dis[ch]:\n",
    "                dis[ch] = d + cost[node][ch]\n",
    "                heapq.heappush(q, (dis[ch], ch))\n",
    "\n",
    "    return dis\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        cost = [{} for _ in range(n)]\n",
    "        for u, v, c in roads:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            cost[u][v] = c\n",
    "            cost[v][u] = c\n",
    "\n",
    "        dis = []\n",
    "        for i in range(n):\n",
    "            dis.append(dijkstra(g, cost, i))\n",
    "        min_dis = dis[0][-1]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(node, d):\n",
    "            if node == n - 1:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for ch in g[node]:\n",
    "                if d + cost[node][ch] + dis[ch][-1] != min_dis:\n",
    "                    continue\n",
    "                res += dfs(ch, d + cost[node][ch])\n",
    "            return res % kmod\n",
    "        \n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, c in roads:\n",
    "            g[a].append((b, c))\n",
    "            g[b].append((a, c))\n",
    "\n",
    "        d = {}\n",
    "        h = [(0, 0)]\n",
    "        while h:\n",
    "            dis, a = heappop(h)\n",
    "            if a not in d:\n",
    "                d[a] = dis\n",
    "                for b, c in g[a]:\n",
    "                    heappush(h, (dis + c, b))\n",
    "\n",
    "        @cache\n",
    "        def dfs(a):\n",
    "            if not a:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for b, c in g[a]:\n",
    "                if d[a] - d[b] == c:\n",
    "                    res += dfs(b)\n",
    "            return res % mod\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        res = dfs(n - 1)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "\n",
    "        dp=[1]+[0]*(n-1)\n",
    "        #mindis=[1000000000000]*n\n",
    "        mod=10**9+7\n",
    "\n",
    "        g=defaultdict(list)\n",
    "        for ii in range(0,len(roads)):\n",
    "            g[roads[ii][0]].append((roads[ii][1],roads[ii][2]))\n",
    "            g[roads[ii][1]].append((roads[ii][0],roads[ii][2]))\n",
    "\n",
    "        print(g)\n",
    "\n",
    "        def dijkstra(graph,start):\n",
    "            dist=[-1]*n\n",
    "            dist[start]=0\n",
    "            used=set()\n",
    "            q=[(0,start)]\n",
    "\n",
    "            while q:\n",
    "                print(q)\n",
    "                temp=heapq.heappop(q)\n",
    "                h1=temp[1]\n",
    "                h0=temp[0]\n",
    "                #if(h1 in used):\n",
    "                #    continue\n",
    "                used.add(h1)\n",
    "                for (v,weight) in graph[h1]:\n",
    "                    print(v,weight)\n",
    "                    target=h0+weight\n",
    "                    if(dist[v]==-1 or target<dist[v]):\n",
    "                        dist[v]=target\n",
    "                        heapq.heappush(q,(dist[v],v))\n",
    "                        dp[v]=dp[h1]\n",
    "                    elif(dist[v]==target):\n",
    "                        dp[v]+=dp[h1]\n",
    "\n",
    "            return dp\n",
    "\n",
    "       \n",
    "        #b=dijkstra(g,0)[1]+dijkstra(g,1)[n-1]\n",
    "        #print(b)\n",
    "        dp1=dijkstra(g,0)\n",
    "        print(dp1)\n",
    "\n",
    "        return dp1[n-1]%mod\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[]for _ in range(n)]\n",
    "        for u, v, t in roads:\n",
    "            g[u].append((v, t))\n",
    "            g[v].append((u, t))\n",
    "\n",
    "        dist = self.dijsktra(g, 0)\n",
    "\n",
    "        g1 = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j, d in g[i]:\n",
    "                if dist[j] == dist[i] + d:\n",
    "                    g1[i].append(j)\n",
    "                # if dist[i] == dist[j] + d:\n",
    "                #     g1[j].append(i)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n - 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for j in g1[i]:\n",
    "                res += dfs(j)\n",
    "            return res\n",
    "        return dfs(0) % (10**9 + 7)\n",
    "\n",
    "    \n",
    "    def dijsktra(self, g, start):\n",
    "        pq = [(0, start)]\n",
    "        n = len(g)\n",
    "        dist = [inf] * n\n",
    "        dist[start] = 0\n",
    "        st = [False] * n\n",
    "        while pq:\n",
    "            d, ver = heappop(pq)\n",
    "            if st[ver]:\n",
    "                continue\n",
    "            st[ver] = True\n",
    "            for i, d2  in g[ver]:\n",
    "                dist[i] = min(dist[i], d + d2)\n",
    "                if not st[i]:\n",
    "                    heappush(pq, (dist[i], i))\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, v=-1, w=-1, nex=None):\n",
    "        self.v = v\n",
    "        self.w = w\n",
    "        self.nex = nex  \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        inf = 1 << 64\n",
    "        adjl = [None] * n\n",
    "        for u, v, w in roads:\n",
    "            adjl[u] = Node(v, w, adjl[u])\n",
    "            adjl[v] = Node(u, w, adjl[v])\n",
    "\n",
    "        dist = [inf] * (n - 1) + [0]\n",
    "        heap = [[dist[n - 1], n - 1]]\n",
    "        while heap:\n",
    "            d, u = heappop(heap)\n",
    "            if dist[u] < d:\n",
    "                continue\n",
    "\n",
    "            node = adjl[u]\n",
    "            while node is not None:\n",
    "                v, w = node.v, node.w\n",
    "                if dist[u] + w < dist[v]:\n",
    "                    dist[v] = dist[u] + w\n",
    "                    heappush(heap, [dist[v], v])\n",
    "                node = node.nex\n",
    "\n",
    "        dic = {n - 1: 1}\n",
    "\n",
    "        def dfs(u: int) -> int:\n",
    "            if u in dic:\n",
    "                return dic[u]\n",
    "            node = adjl[u]\n",
    "            dic[u] = 0\n",
    "            while node is not None:\n",
    "                v, w = node.v, node.w\n",
    "                if dist[u] - dist[v] == w:\n",
    "                    dic[u] += dfs(v)\n",
    "                    dic[u] %= mod\n",
    "                node = node.nex\n",
    "            return dic[u]\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # dijkstra算法计算起点到各个点的最短路径\n",
    "        edges = collections.defaultdict(list)\n",
    "        min_distances = [float('inf')]*n\n",
    "        min_distances[0] = 0\n",
    "        for x, y, c in roads:\n",
    "            edges[x].append((y, c))\n",
    "            edges[y].append((x, c))\n",
    "        pq = []\n",
    "        seen = set()\n",
    "        heapq.heappush(pq, (0, 0))\n",
    "        while len(seen)!=n:\n",
    "            min_dis, curr_node = heapq.heappop(pq)\n",
    "            print(curr_node, min_dis)\n",
    "            if curr_node in seen:\n",
    "                continue\n",
    "            else:\n",
    "                seen.add(curr_node)\n",
    "                min_distances[curr_node] = min_dis\n",
    "                for nxt_node, c in edges[curr_node]:\n",
    "                    heapq.heappush(pq, (c+min_dis,nxt_node))\n",
    "        # 构造有向图\n",
    "        graph = collections.defaultdict(list)\n",
    "        for x, y, c in roads:\n",
    "            if min_distances[x]-min_distances[y] == c:\n",
    "                graph[y].append(x)\n",
    "            if min_distances[y]-min_distances[x] == c:\n",
    "                graph[x].append(y)\n",
    "        MOD = 10**9+7\n",
    "        # print(graph)\n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            if node == n-1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for nxt_node in graph[node]:\n",
    "                res += dfs(nxt_node)\n",
    "            return res%MOD\n",
    "        # print(min_distances)\n",
    "        return dfs(0)\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "#         mod = 10**9 + 7\n",
    "        \n",
    "#         dist = [[float(\"inf\")] * n for _ in range(n)]\n",
    "#         for i in range(n):\n",
    "#             dist[i][i] = 0\n",
    "        \n",
    "#         for x, y, z in roads:\n",
    "#             dist[x][y] = dist[y][x] = z\n",
    "        \n",
    "#         # Floyd 算法求解最短路\n",
    "#         # 完成后，dist[0][i] 即为正文部分的 dist[i]\n",
    "#         # for k in range(n):\n",
    "#         #     for i in range(n):\n",
    "#         #         for j in range(n):\n",
    "#         #             dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n",
    "\n",
    "#         # Dijkstra 算法求解最短路\n",
    "#         # 完成后，dist[0][i] 即为正文部分的 dist[i]\n",
    "#         seen = set()\n",
    "#         for _ in range(n - 1):\n",
    "#             u = None\n",
    "#             for i in range(n):\n",
    "#                 if i not in seen and (not u or dist[0][i] < dist[0][u]):\n",
    "#                     u = i\n",
    "#             seen.add(u)\n",
    "#             for i in range(n):\n",
    "#                 dist[0][i] = min(dist[0][i], dist[0][u] + dist[u][i])\n",
    "\n",
    "#         # 构造图 G\n",
    "#         g = defaultdict(list)\n",
    "#         for x, y, z in roads:\n",
    "#             if dist[0][y] - dist[0][x] == z:\n",
    "#                 g[x].append(y)\n",
    "#             elif dist[0][x] - dist[0][y] == z:\n",
    "#                 g[y].append(x)\n",
    "\n",
    "#         @cache\n",
    "#         def dfs(u: int) -> int:\n",
    "#             if u == n - 1:\n",
    "#                 return 1\n",
    "\n",
    "#             ret = 0\n",
    "#             for v in g[u]:\n",
    "#                 ret += dfs(v)\n",
    "#             return ret % mod\n",
    "        \n",
    "#         ans = dfs(0)\n",
    "#         dfs.cache_clear()\n",
    "#         print(dist[0])\n",
    "#         return ans\n",
    "        \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for r in roads:\n",
    "            u, v, t = r\n",
    "            graph[u].append([v, t])\n",
    "            graph[v].append([u, t])\n",
    "        \n",
    "        PUSH, POP = heapq.heappush, heapq.heappop\n",
    "        h = [(0, 0, 0)]\n",
    "        dist = [float(\"inf\")] * n\n",
    "        ways = [0] * n\n",
    "        ways[0] = 1\n",
    "        while h:\n",
    "            _time, u, prev = POP(h)\n",
    "            \n",
    "            if _time < dist[u]:\n",
    "                dist[u] = _time\n",
    "                ways[u] = ways[prev]\n",
    "            elif _time == dist[u]:\n",
    "                ways[u] += ways[prev]\n",
    "                continue\n",
    "            else:\n",
    "                continue\n",
    "            for v, t in graph[u]:\n",
    "                PUSH(h, (_time + t, v, u))\n",
    "        \n",
    "        return ways[-1] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countPaths(self, n, roads):\n",
    "        d = collections.defaultdict(lambda:collections.defaultdict(int))\n",
    "        for u, v, t in roads:\n",
    "            d[u][v] = t\n",
    "            d[v][u] = t\n",
    "        dist = [-1] * n\n",
    "        dist[0] = 0\n",
    "        times = [0] * n\n",
    "        times[0] = 1\n",
    "        st = []\n",
    "        for v in d[0]:\n",
    "            st.append([d[0][v], v, 0])\n",
    "        heapq.heapify(st)\n",
    "        while st:\n",
    "            while st and dist[st[0][1]] >= 0:\n",
    "                q, u, last = heapq.heappop(st)\n",
    "                if q == dist[u]:\n",
    "                    times[u] += times[last]\n",
    "            if st:\n",
    "                q, u, last = heapq.heappop(st)\n",
    "                dist[u] = q\n",
    "                times[u] += times[last]\n",
    "                for v in d[u]:\n",
    "                    heapq.heappush(st, [d[u][v] + dist[u], v, u])\n",
    "        return times[-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import functools\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        edges = collections.defaultdict(list)\n",
    "        for a, b, v in roads:\n",
    "            edges[a].append((b, v))\n",
    "            edges[b].append((a, v))\n",
    "\n",
    "        q = [[0, 0]]\n",
    "        heapq.heapify(q)\n",
    "        mark = [-1] * n\n",
    "        while q:\n",
    "            t, node = heapq.heappop(q)\n",
    "            if mark[node] == -1:\n",
    "                mark[node] = t\n",
    "                for nextNode, v in edges[node]:\n",
    "                    heapq.heappush(q, [v + t, nextNode])\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(curNode: int):\n",
    "            if curNode == n - 1:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for nextNode, t in edges[curNode]:\n",
    "                if mark[nextNode] - mark[curNode] == t:\n",
    "                    cnt += dfs(nextNode)\n",
    "            return cnt % mod\n",
    "\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Graph: \n",
    "    def __init__(self,vnum,attr=None): \n",
    "        self.aje = dict()\n",
    "        self.vnum = vnum\n",
    "        self.pnum=0\n",
    "        self.distfirst=[]\n",
    "\n",
    "    def addEdge(self,u,v,w=0): \n",
    "        self.aje.setdefault(u,{})\n",
    "        if v not in self.aje[u]:\n",
    "            self.aje[u].setdefault('v',list())\n",
    "            self.aje[u]['v'].append(v) \n",
    "            self.aje[u][v]=w\n",
    "\n",
    "    @cache\n",
    "    def dfs(self,u):\n",
    "        #print(u,left)\n",
    "        num=0\n",
    "        if u==self.vnum-1:\n",
    "            num+=1\n",
    "        else:\n",
    "            tmp= [_ve for _ve in self.aje[u]['v']]\n",
    "            for _ve in tmp:\n",
    "                if self.distfirst[_ve]-self.distfirst[u]==self.aje[u][_ve]:\n",
    "                    num+=self.dfs(_ve)\n",
    "        return num %(10**9+7)        \n",
    "\n",
    "    def dijkstra(self,src):\n",
    "        #n为源点，dijkstra单源最短路径,n到各点的最短距离，就是各点到n的最短距离\n",
    "        dist = [float('inf') for _ in range(self.vnum)]\n",
    "        dist[0] = 0\n",
    "        visited = set()\n",
    "        minHeap = [(0,src)]\n",
    "        while minHeap:\n",
    "            cloestDist, cloestNode = heapq.heappop(minHeap) #距离源节点最近的结点\n",
    "            if cloestNode in visited:           #已经在选中的区域里了，就不要再选了\n",
    "                continue\n",
    "            visited.add(cloestNode)             #未选择的点中，这是最小的。正式加入区域\n",
    "            for nxt in self.aje[cloestNode]['v']:      #更新与它相连接的点\n",
    "                if dist[cloestNode] + self.aje[cloestNode][nxt] < dist[nxt]:\n",
    "                    dist[nxt] = dist[cloestNode] + self.aje[cloestNode][nxt]\n",
    "                    heapq.heappush(minHeap, (dist[nxt], nxt))  \n",
    "        self.distfirst= dist\n",
    "        #print(dist)\n",
    "        return dist\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        if n==1:return 1\n",
    "        gr = Graph(n)\n",
    "        for vb,ve,wei in roads:\n",
    "            gr.addEdge(vb,ve,wei)\n",
    "            gr.addEdge(ve,vb,wei)\n",
    "        gr.dijkstra(0)     \n",
    "        return gr.dfs(0) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        def shortestPath(node1) -> int:\n",
    "            dis = [inf]*n \n",
    "            dis[node1] = 0\n",
    "            q = [(0,node1)]\n",
    "            vis = set()\n",
    "            while q:\n",
    "                _,u = heapq.heappop(q)\n",
    "                #if u==node2: return dis[node2]\n",
    "                if u in vis: continue\n",
    "                vis.add(u)\n",
    "                for v, w in g[u]:\n",
    "                    if dis[v] > dis[u] + w:\n",
    "                        dis[v] = dis[u] + w\n",
    "                        heapq.heappush(q, (dis[v], v)) \n",
    "            return dis#[node2]\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y,v in roads:\n",
    "            g[x].append((y,v))\n",
    "            g[y].append((x,v))\n",
    "        mat=shortestPath(n-1)\n",
    "        m=mat[0]\n",
    "        mod=10**9+7\n",
    "        vis=[0]*n\n",
    "        vis[0]=1 \n",
    "        @cache\n",
    "        def dfs(i,t):\n",
    "            nonlocal n,mod \n",
    "            ans=0\n",
    "            if t<mat[i]: return 0\n",
    "            if i==n-1: return 1\n",
    "            #vis[i]=1\n",
    "            for j,v in g[i]:\n",
    "                if not vis[j]:\n",
    "                    vis[j]=1\n",
    "                    ans+=dfs(j,t-v)\n",
    "                    vis[j]=0\n",
    "            return ans%mod\n",
    "        return dfs(0,m)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        def shortestPath(node1) -> int:\n",
    "            dis = [inf]*n \n",
    "            dis[node1] = 0\n",
    "            q = [(0,node1)]\n",
    "            vis = set()\n",
    "            while q:\n",
    "                _,u = heapq.heappop(q)\n",
    "                #if u==node2: return dis[node2]\n",
    "                if u in vis: continue\n",
    "                vis.add(u)\n",
    "                for v, w in g[u]:\n",
    "                    if dis[v] > dis[u] + w:\n",
    "                        dis[v] = dis[u] + w\n",
    "                        heapq.heappush(q, (dis[v], v)) \n",
    "            return dis#[node2]\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y,v in roads:\n",
    "            g[x].append((y,v))\n",
    "            g[y].append((x,v))\n",
    "        mat=shortestPath(n-1)\n",
    "        m=mat[0]\n",
    "        mod=10**9+7\n",
    "        vis=[0]*n\n",
    "        vis[0]=1 \n",
    "        @cache\n",
    "        def dfs(i,t):\n",
    "            nonlocal n,mod \n",
    "            ans=0\n",
    "            if t<mat[i]: return 0\n",
    "            if i==n-1: return 1\n",
    "            #vis[i]=1\n",
    "            for j,v in g[i]:\n",
    "                if not vis[j]:\n",
    "                    vis[j]=1\n",
    "                    ans+=dfs(j,t-v)\n",
    "                    vis[j]=0\n",
    "            return ans%mod\n",
    "        return dfs(0,m)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # 我觉得是最短路稍微改一下就行了\n",
    "        g = [[] for _ in range(n)]\n",
    "        weight = defaultdict(int)\n",
    "        for u, v, w in roads:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            weight[(u, v)] = w\n",
    "            weight[(v, u)] = w\n",
    "\n",
    "        dist = [0 if i == 0 else inf for i in range(n)]\n",
    "        cnt = [1 if i == 0 else 0 for i in range(n)]\n",
    "        h = []\n",
    "        for x, d in enumerate(dist):\n",
    "            heappush(h, [d, x])\n",
    "        \n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if dist[x] != d:\n",
    "                continue\n",
    "            for y in g[x]:\n",
    "                if dist[x] + weight[(y, x)] < dist[y]:\n",
    "                    dist[y] = dist[x] + weight[(y, x)]\n",
    "                    cnt[y] = cnt[x]\n",
    "                    heappush(h, [dist[y], y])\n",
    "                elif dist[x] + weight[(y, x)] == dist[y]:\n",
    "                    cnt[y] += cnt[x]\n",
    "\n",
    "        return cnt[-1] % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        mod = 10**9+7\n",
    "        time = [inf for _ in range(n)]\n",
    "        time[-1] = 0\n",
    "        edges = defaultdict(list)\n",
    "        for i,j,v in roads:\n",
    "            edges[i].append([j,v])\n",
    "            edges[j].append([i,v])\n",
    "        queue = [[0,n-1]]\n",
    "        while queue:\n",
    "            cost,cur = heappop(queue)\n",
    "            if cost > time[cur]:\n",
    "                continue\n",
    "            for new,v in edges[cur]:\n",
    "                if v + cost < time[new]:\n",
    "                    time[new] = v + cost\n",
    "                    heappush(queue,[v+cost,new])\n",
    "        @cache\n",
    "        def dfs(cur=0,t=time[0]):\n",
    "            if cur == n-1:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for new,v in edges[cur]:\n",
    "                if v + time[new] <= t:\n",
    "                    ans += dfs(new,t-v)\n",
    "            return ans%mod\n",
    "        return dfs()\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Graph: \n",
    "    def __init__(self,vnum,attr=None): \n",
    "        self.aje = dict()\n",
    "        self.vnum = vnum\n",
    "        self.pnum=0\n",
    "        self.distfirst=[]\n",
    "\n",
    "    def addEdge(self,u,v,w=0): \n",
    "        self.aje.setdefault(u,{})\n",
    "        if v not in self.aje[u]:\n",
    "            self.aje[u].setdefault('v',list())\n",
    "            self.aje[u]['v'].append(v) \n",
    "            self.aje[u][v]=w\n",
    "\n",
    "    def dfs_v0(self,u,left,paths):\n",
    "        #print(u,left,paths)\n",
    "        num=0\n",
    "        if u==self.vnum-1:\n",
    "            num+=1\n",
    "        else:\n",
    "            tmp= [_ve for _ve in self.aje[u]['v'] if _ve not in paths ]\n",
    "            for _ve in tmp:\n",
    "                if left>=self.aje[u][_ve]:\n",
    "                    num+=self.dfs(_ve,left-self.aje[u][_ve],paths+[_ve])\n",
    "                else:\n",
    "                   break\n",
    "        return num %(10**9+7)\n",
    "\n",
    "    @cache\n",
    "    def dfs(self,u,left):\n",
    "        #print(u,left)\n",
    "        num=0\n",
    "        if u==self.vnum-1:\n",
    "            num+=1\n",
    "        else:\n",
    "            tmp= [_ve for _ve in self.aje[u]['v']]\n",
    "            \n",
    "            for _ve in tmp:\n",
    "                #print(_ve,self.distfirst[u],self.distfirst[_ve])\n",
    "                if self.distfirst[_ve]-self.distfirst[u]==self.aje[u][_ve]:\n",
    "                    num+=self.dfs(_ve,left-self.aje[u][_ve])\n",
    "                #else:\n",
    "                #   break\n",
    "        return num %(10**9+7)        \n",
    "\n",
    "    def dijkstra(self,src):\n",
    "        #n为源点，dijkstra单源最短路径,n到各点的最短距离，就是各点到n的最短距离\n",
    "        dist = [float('inf') for _ in range(self.vnum)]\n",
    "        dist[0] = 0\n",
    "        visited = set()\n",
    "        minHeap = [(0,src)]\n",
    "        while minHeap:\n",
    "            cloestDist, cloestNode = heapq.heappop(minHeap) #距离源节点最近的结点\n",
    "            if cloestNode in visited:           #已经在选中的区域里了，就不要再选了\n",
    "                continue\n",
    "            visited.add(cloestNode)             #未选择的点中，这是最小的。正式加入区域\n",
    "            for nxt in self.aje[cloestNode]['v']:      #更新与它相连接的点\n",
    "                if dist[cloestNode] + self.aje[cloestNode][nxt] < dist[nxt]:\n",
    "                    dist[nxt] = dist[cloestNode] + self.aje[cloestNode][nxt]\n",
    "                    heapq.heappush(minHeap, (dist[nxt], nxt))  \n",
    "        #self.distfirst= dist\n",
    "        #print(dist)\n",
    "        for k in self.aje: self.aje[k]['v']=sorted(self.aje[k]['v'],key=lambda x:self.aje[k][x])\n",
    "        return dist\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        if n==1:return 1\n",
    "        gr = Graph(n)\n",
    "        for vb,ve,wei in roads:\n",
    "            gr.addEdge(vb,ve,wei)\n",
    "            gr.addEdge(ve,vb,wei)\n",
    "        gr.distfirst=gr.dijkstra(0)     \n",
    "        #gr.distfirst= gr.dijkstra(n-1) \n",
    "        #print(gr.distfirst)\n",
    "        #return   \n",
    "        return gr.dfs(0,gr.distfirst[n-1]) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        mod = 10**9+7\n",
    "        record = [inf for _ in range(n)]\n",
    "        record[-1] = 0\n",
    "        edges = defaultdict(list)\n",
    "        for i,j,v in roads:\n",
    "            edges[i].append([j,v])\n",
    "            edges[j].append([i,v])\n",
    "        queue = [[0,n-1]]\n",
    "        while queue:\n",
    "            cost,cur = heappop(queue)\n",
    "            if cost > record[cur]:\n",
    "                continue\n",
    "            for new,v in edges[cur]:\n",
    "                if v + cost < record[new]:\n",
    "                    record[new] = v + cost\n",
    "                    heappush(queue,[v+cost,new])\n",
    "\n",
    "        time = record[0]\n",
    "        @cache\n",
    "        def dfs(i=0,t=time):\n",
    "            if i == n-1:return 1\n",
    "            ans = 0\n",
    "            for k,v in edges[i]:\n",
    "                if v + record[k]<= t:\n",
    "                    ans += dfs(k,t-v)\n",
    "            return ans%mod\n",
    "        return dfs()\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        G = defaultdict(list)\n",
    "        for (a, b, c) in roads:\n",
    "            G[a].append([b, c])\n",
    "            G[b].append([a, c])\n",
    "\n",
    "        que = []\n",
    "        path = [0] * n\n",
    "        dist = [float('inf')] * n\n",
    "        heappush(que,[0, 0])\n",
    "        dist[0] = 0\n",
    "        path[0] = 1\n",
    "        while que:\n",
    "            (sm, u) = que[0]\n",
    "            heappop(que)\n",
    "            for (v, spend) in G[u]:\n",
    "                if dist[u] + spend < dist[v]:\n",
    "                    dist[v] = dist[u] + spend\n",
    "                    heappush(que, [dist[v], v])\n",
    "\n",
    "        mod = int(1e9) + 7\n",
    "        @cache\n",
    "        def dfs(u):\n",
    "            if u == n - 1:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for v, spend in G[u]:\n",
    "                if (dist[v] == dist[u] + spend):\n",
    "                    ans = (ans + dfs(v)) % mod\n",
    "            return ans\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        mod = 10**9+7\n",
    "        time = [inf for _ in range(n)]\n",
    "        time[-1] = 0\n",
    "        edges = defaultdict(list)\n",
    "        for i,j,v in roads:\n",
    "            edges[i].append([j,v])\n",
    "            edges[j].append([i,v])\n",
    "        queue = [[0,n-1]]\n",
    "        while queue:\n",
    "            cost,cur = heappop(queue)\n",
    "            if cost > time[cur]:\n",
    "                continue\n",
    "            for new,v in edges[cur]:\n",
    "                if v + cost < time[new]:\n",
    "                    time[new] = v + cost\n",
    "                    heappush(queue,[v+cost,new])\n",
    "        @cache\n",
    "        def dfs(cur=0,t=time[0]):\n",
    "            if cur == n-1:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for new,v in edges[cur]:\n",
    "                if v + time[new] == t:\n",
    "                    ans += dfs(new,t-v)\n",
    "            return ans%mod\n",
    "        return dfs()\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        mod = 10**9+7\n",
    "        record = [inf for _ in range(n)]\n",
    "        record[-1] = 0\n",
    "        edges = defaultdict(list)\n",
    "        for i,j,v in roads:\n",
    "            edges[i].append([j,v])\n",
    "            edges[j].append([i,v])\n",
    "        queue = [[0,n-1]]\n",
    "        while queue:\n",
    "            cost,cur = heappop(queue)\n",
    "            if cost > record[cur]:\n",
    "                continue\n",
    "            for new,v in edges[cur]:\n",
    "                if v + cost < record[new]:\n",
    "                    record[new] = v + cost\n",
    "                    heappush(queue,[v+cost,new])\n",
    "\n",
    "        time = record[0]\n",
    "        @cache\n",
    "        def dfs(i=0,t=time):\n",
    "            if i == n-1:return 1\n",
    "            ans = 0\n",
    "            for k,v in edges[i]:\n",
    "                if v + record[k]<= t:\n",
    "                    ans += dfs(k,t-v)\n",
    "            return ans%mod\n",
    "        return dfs()\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        adjl = [[] for _ in range(0 , n)]\n",
    "        for u, v, w in roads:\n",
    "            adjl[u].append([v, w])\n",
    "            adjl[v].append([u, w])\n",
    "\n",
    "        dp, dist = {}, {}\n",
    "        heap = [[0, n - 1]]\n",
    "        while heap:\n",
    "            d, u = heappop(heap)\n",
    "            if u in dist:\n",
    "                continue\n",
    "\n",
    "            dist[u] = d\n",
    "            dp[u] = 1 if u == n - 1 else 0\n",
    "            for v, w in adjl[u]:\n",
    "                if v in dist and dist[u] - dist[v] == w:\n",
    "                    dp[u] = (dp[u] + dp[v]) % mod\n",
    "                heappush(heap, [d + w, v])\n",
    "\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(node:int)->int:\n",
    "            if node == 0:\n",
    "                return 1\n",
    "            result = 0\n",
    "            for neigh in graph[node]:\n",
    "                if dist[node] - dist[neigh] == cost[node,neigh]:\n",
    "                    result += dfs(neigh)\n",
    "            return result % MOD\n",
    "\n",
    "        graph = defaultdict(set)\n",
    "        cost = defaultdict(int)\n",
    "        for a,b,c in roads:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "            cost[(a,b)] = cost[(b,a)] = c\n",
    "        MOD = 10**9 + 7\n",
    "        heap = [(0,0)]\n",
    "        dist = defaultdict(int)\n",
    "\n",
    "        while heap:\n",
    "            used_time, node = heappop(heap)\n",
    "            if node in dist and dist[node] <= used_time:\n",
    "                continue\n",
    "            dist[node] = used_time\n",
    "\n",
    "            for neigh in graph[node]:\n",
    "                ntime = used_time + cost[node,neigh]\n",
    "                if neigh in dist and dist[neigh] <= ntime:\n",
    "                    continue\n",
    "                heappush(heap,(ntime,neigh))\n",
    "\n",
    "        return dfs(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        graph = collections.defaultdict(set)\n",
    "        for u, v, t in roads:\n",
    "            graph[u].add((v, t))\n",
    "            graph[v].add((u, t))\n",
    "        distance = [-1] * n\n",
    "        pq = [(0,0)]\n",
    "\n",
    "        while pq:\n",
    "            d, node = heapq.heappop(pq)\n",
    "            if distance[node] >= 0:\n",
    "                continue\n",
    "            distance[node] = d\n",
    "            for nxt, t in graph[node]:\n",
    "                if distance[nxt] >= 0:\n",
    "                    continue\n",
    "                heapq.heappush(pq, (t + d, nxt))\n",
    "        # print(distance)\n",
    "\n",
    "        memo = {}\n",
    "        def dfs(node, d):\n",
    "            if distance[node] != d:\n",
    "                return 0\n",
    "            if node == 0:\n",
    "                return 1\n",
    "            \n",
    "            if node in memo:\n",
    "                return memo[node]\n",
    "            val = 0\n",
    "            for nxt, t in graph[node]:\n",
    "                val += dfs(nxt, d - t)\n",
    "                val %= MOD\n",
    "            memo[node] = val\n",
    "            return val\n",
    "        return dfs(n-1, distance[-1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        edge=collections.defaultdict(list)\n",
    "        for a,b,d in roads:\n",
    "            edge[a].append([b,d])\n",
    "            edge[b].append([a,d])\n",
    "        dis=[float(\"inf\")]*n\n",
    "        way=[0]*n\n",
    "        way[0]=1\n",
    "        dis[0]=0\n",
    "        l=[]\n",
    "        heapq.heappush(l,[0,0,0])\n",
    "        put=[[False for _ in range(n)] for _ in range(n)]\n",
    "        while l:\n",
    "            d,i,f=heapq.heappop(l)\n",
    "            \n",
    "            if i!=0:\n",
    "                if d >dis[i]:\n",
    "                    continue\n",
    "                elif d<dis[i]:\n",
    "                    dis[i]=d\n",
    "                    way[i]=(way[i]+way[f])%1000000007\n",
    "                else:\n",
    "                    way[i]=(way[i]+way[f])%1000000007\n",
    "            #print(i,f,d,dis[i],way[i])\n",
    "            for j,k in edge[i]:\n",
    "                if way[j]==0:\n",
    "                    if not put[j][i]:\n",
    "                        put[j][i]=True\n",
    "                        heapq.heappush(l,[d+k,j,i])\n",
    "        #print(way)\n",
    "        return way[n-1] %1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        graph = collections.defaultdict(list)\n",
    "        vals = collections.defaultdict(int)\n",
    "        for a, b, v in roads:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "            vals[a, b] = v\n",
    "            vals[b, a] = v\n",
    "\n",
    "        q = [[0, 0]]\n",
    "        heapq.heapify(q)\n",
    "        mark = [-1] * n\n",
    "        while q:\n",
    "            t, node = heapq.heappop(q)\n",
    "            if mark[node] == -1:\n",
    "                mark[node] = t\n",
    "                for nextNode in graph[node]:\n",
    "                    heapq.heappush(q, [vals[node, nextNode] + t, nextNode])\n",
    "\n",
    "        @functools.cache\n",
    "        def dfs(curNode: int):\n",
    "            if curNode == n - 1:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for nextNode in graph[curNode]:\n",
    "                if vals[curNode, nextNode] + mark[curNode] == mark[nextNode]:\n",
    "                    cnt += dfs(nextNode)\n",
    "            cnt %= mod\n",
    "            return cnt\n",
    "\n",
    "        res = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "mod = pow(10,9)+7\n",
    "\n",
    "def gatherSame(follows):\n",
    "    k2f = dict()\n",
    "    for follow in follows:\n",
    "        p,t,c = follow\n",
    "        key = \"{}-{}\".format(p, t)\n",
    "        if key not in k2f:\n",
    "            k2f[key] = [p,t,c]\n",
    "        else:\n",
    "            k2f[key][2] += c\n",
    "    new_follows = []\n",
    "    for k in k2f:\n",
    "        f = k2f[k]\n",
    "        f[2] = f[2] % mod\n",
    "        new_follows.append(f)\n",
    "    return new_follows\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "\n",
    "        p2follows = dict()\n",
    "        for i in range(n):\n",
    "            p2follows[i] = []\n",
    "\n",
    "        for pair in roads:\n",
    "            u,v,t = pair\n",
    "            p2follows[u].append([v,t,1])\n",
    "            p2follows[v].append([u,t,1])\n",
    "\n",
    "        p2v = {\n",
    "            0:[0,1]\n",
    "        }\n",
    "\n",
    "        follows = p2follows[0]\n",
    "        while len(follows) > 0:\n",
    "            follows = gatherSame(follows)\n",
    "            follows_s = sorted(follows, key=operator.itemgetter(1))\n",
    "            p,t,c = follows_s[0]\n",
    "            # print (\"follows_s:{}\".format(follows_s))\n",
    "            # print (\"\\tappend {},{},{}\".format(p,t,c))\n",
    "            if p not in p2v:\n",
    "                p2v[p] = [t,c]\n",
    "            else:\n",
    "                break\n",
    "\n",
    "            # next\n",
    "            pcount = p2v[p][1]\n",
    "            next_follows = follows_s[1:]\n",
    "\n",
    "            ps = p2follows[p]\n",
    "            # print (\"\\t\\tp's follows:{}, {}\".format(p, ps))\n",
    "            for npair in ps:\n",
    "                np, nt,nc = npair\n",
    "                if np in p2v:\n",
    "                    # print (\"\\t\\talready exists in p2v:{}, {}\".format(np, p2v[np]))\n",
    "                    continue\n",
    "                next_follows.append([np,t+nt,c])\n",
    "\n",
    "            follows = next_follows\n",
    "            # print (\"\\tp2v:\", p2v)\n",
    "        return p2v[n-1][1]%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n",
    "        m = len(roads)\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        for a, b, w in roads:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))\n",
    "\n",
    "        dists = [inf] * n\n",
    "\n",
    "        q = [(0, 0)]\n",
    "\n",
    "        while q:\n",
    "            d, x = heappop(q)\n",
    "\n",
    "            if d < dists[x]:\n",
    "                dists[x] = d\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "            for y, w in g[x]:\n",
    "                nd = w + d\n",
    "\n",
    "                if nd < dists[y]:\n",
    "                    heappush(q, (nd, y))\n",
    "\n",
    "        mad = dists[n - 1]\n",
    "\n",
    "        @cache\n",
    "        def dp(x, d):\n",
    "            # if d > mad:\n",
    "            #     return 0\n",
    "            \n",
    "            if x == n - 1:\n",
    "                return 1\n",
    "\n",
    "            ret = 0\n",
    "            for y, w in g[x]:\n",
    "                if dists[y] - dists[x] == w:\n",
    "                    ret += dp(y, d + w)\n",
    "                    ret %= MOD\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
